10881 - Piotr's Ants

[wook]

I have solved this problem
(i think it would be enough fast to ACCEPT, if my output is correct)
but i got WA(WRONG ANSWER) in 0.227 sec

i can't find critical input data that makes different between my output and correct output,
but for it when more than two ants are at the same location.

that is, can this input exist, if more than two ants are at the same start location?
if it exist, what do i have to output?

Code: Select all

10 1 3
3 L
3 R
3 L

if there is a input like above,

i think

2 Turning
2 Turning
4 R

2 Turning
4 R
2 Turning

..etc..

is correct answer,

but the ants that is located at 2 are not TURNING!!

i'm confused,
please help me.

[Abednego]

Two ants are never at the same starting location.

Make sure that you print the ants in the correct order.

[Jan]

What is the output of the following input set?

Input:

Code: Select all

6
10 1 2
3 R
4 L
10 1 2
1 R 
2 L
10 1 2
1 R 
3 L
3 2 2
1 R
3 L
3 1 2
1 R 
3 L
10 2 3
1 R
2 R
3 R

Thanks in advance.

[wook]

my output for input above :

for

Case #1:
3 L
4 R

Case #2:
1 L
2 R

Case #3:
2 Turning
2 Turning

Case #4:
1 L
3 R

Case #5:
2 Turning
2 Turning

Case #6:
3 R
4 R
5 R

isn't it correct?

[wook]

thank you, all.

i rewrote my source code and finally got AC

it's fast ! and ranked first

[mysword]

what's the method used for this problem?
I think simple simulation can cause TLE

[Cho]

Sorting

[wahab]

Can you give more hints?

[Angeh]

any hints to solve this problem ....

[..]

Hope the one asking about hint is still interesting in this problem.

spoiler alert














Consider we have 3 ants
Ant_a at position P_a, facing R
Ant_b at position P_b, facing R
Ant_c at position P_c, facing L
with P_a < P_b < P_c

If you simulate the scenario you will find that the ant Ant_a will turn around at time (P_c - P_a)/2, just like the ant_b doesn't exist!
When generalize the idea you will find that you can imagine the ant will not turn around, but pass through each other at collision. So the remaining is how to map the pass-through scenario to the turn-around scenario. This part I leave it to you to have fun

[Angeh]

Thanks for your hints ....
i konw these facts, but i'm cofused how to use them ...
i have thought about it for 2 days but still .... nothing ...

[messiNayan]

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;

#define SIZE 10000

typedef struct
{
char direction;
int ant_no;
double location;
}STATUS;

typedef struct
{
int r;
int l;
}PAIR;

bool compare1(STATUS i, STATUS j)
{
return i.location < j.location;
}

bool compare2(STATUS i, STATUS j)
{
return i.ant_no < j.ant_no;
}

int main(void)
{
int i, j, l, n, case_no, num_of_cases, r_index, r_location;
double t, dist, temp_dist;

STATUS ants_status[SIZE];
PAIR pair[500];

scanf("%d", &num_of_cases);

case_no = 1;
while (case_no <= num_of_cases)
{
memset(ants_status, 0, SIZE);
scanf("%d%lf%d", &l, &t, &n);
i = 0;
while (i < n)
{
scanf("%lf %c", &ants_status.location, &ants_status.direction);
ants_status.ant_no = i;
i++;
}
sort(ants_status, ants_status + n, compare1);




while (1)
{
i = 0;
j = 1;
r_location = -1;
temp_dist = 0xffff - 1;
dist = 0xffff - 1;
memset(pair, 0, 500);

while (i < n)
{
if (ants_status.direction == 'R')
{
r_index = i;
r_location = ants_status.location;
}
else
{
if (r_location != -1)
{
temp_dist = (ants_status.location - r_location) / 2.0;
r_location = -1;

if (temp_dist < dist)
{
dist = temp_dist;
pair[0].r = r_index;
pair[0].l = i;

}
else if (temp_dist == dist)
{
pair[j].r = r_index;
pair[j].l = i;
j++;
}
}
}
i++;
}

if (dist == t)
{
for (i = 0; i < n; i++)
{
if (ants_status.direction == 'R')
ants_status.location += dist;
else
ants_status.location -= dist;

}

for (i = 0; i < j; i++)
{
ants_status[pair.l].direction = 'T';
ants_status[pair[i].r].direction = 'T';
}
break;
}
else if (dist < t)
{
t -= dist;
for (i = 0; i < n; i++)
{
if (ants_status[i].direction == 'R')
ants_status[i].location += dist;
else
ants_status[i].location -= dist;
}

for (i = 0; i < j; i++)
{
ants_status[pair[i].l].direction = 'R';
ants_status[pair[i].r].direction = 'L';
}

dist = 0xffff;

}
else
{
for (i = 0; i < n; i++)
{
if (ants_status[i].direction == 'R')
ants_status[i].location += t;
else
ants_status[i].location -= t;

}
break;
}
}

sort(ants_status, ants_status + n, compare2);

printf("Case #%d:\n", case_no);

for (i = 0; i < n; i++)
{
if (ants_status[i].location > l)
printf("Fell off\n");
else
{
if (ants_status[i].direction == 'T')
printf("%d Turning\n", (int)ants_status[i].location);
else
printf("%d %c\n", (int)ants_status[i].location, ants_status[i].direction);

}
}

case_no++;
}



return 0;
}

I think my algorithm is faster than trivial solution but still getting time limit exit

[feodorv]

I think my algorithm is faster than trivial solution but still getting time limit exit

Sorry, your algorithm is not fast enough. In truth it is very slow. Please, try my input on uDebug...