#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