ants.cpp
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int L,A;
struct Mravenec {
int Pos;
int Cas;
int Dir;
int FallT;
int SPos;
};
int Kolize[100000];
int KSize;
int KLevy,KPravy;
int KTime,KPos,KPos2;
bool ACmp(struct Mravenec M1,struct Mravenec M2) {
return (M1.Pos < M2.Pos);
};
vector<Mravenec> An;
int main() {
int i;
char c;
int X;
int Max;
int MaxF;
struct Mravenec Mr;
struct Mravenec LMr,RMr;
while (scanf("%d%d",&L,&A)==2) {
An.clear();
for (i=0;i<A;i++) {
scanf("%d",&X);
scanf("%c",&c);
while ((c!='R') && (c!='L')) scanf("%c",&c);
Mr.Pos = X*2;
Mr.Cas = 0;
Mr.Dir = (c=='R')?+1:-1;
Mr.SPos = X;
An.push_back(Mr);
};
sort(An.begin(),An.end(),ACmp);
//for (i=0;i<A;i++) printf("%d ",An[i].SPos);
//printf("\n");
KSize = 0;
for (i=1;i<A;i++) {
if ((An[i-1].Dir == +1) && (An[i].Dir == -1)) {
Kolize[KSize++] = i-1;
};
};
while (KSize > 0) {
KLevy = Kolize[--KSize];
KPravy = Kolize[KSize]+1;
//printf("X %d %d",KLevy,KPravy);
//printf("[%d %d %d %d] [%d %d %d %d]\n",An[KLevy].Pos,An[KLevy].Dir,An[KLevy].Cas,An[KLevy].SPos,An[KPravy].Pos,An[KPravy].Dir,An[KPravy].Cas,An[KPravy].SPos);
LMr = An[KLevy];
RMr = An[KPravy];
KPos2 = RMr.Cas-LMr.Cas+LMr.Pos+RMr.Pos;
KPos = KPos2/2;
KTime = An[KLevy].Cas + KPos - An[KLevy].Pos;
//printf("%d %d %d\n",KPos2,KPos,KTime);
// i = An[KLevy].SPos;An[KLevy].SPos = An[KPravy].SPos;An[KPravy].SPos=i;
An[KLevy].Dir = -1;An[KPravy].Dir = +1;
An[KLevy].Cas = KTime;An[KPravy].Cas = KTime;
An[KLevy].Pos = KPos;An[KPravy].Pos = KPos;
//printf("[%d %d %d %d] [%d %d %d %d]\n",An[KLevy].Pos,An[KLevy].Dir,An[KLevy].Cas,An[KLevy].SPos,An[KPravy].Pos,An[KPravy].Dir,An[KPravy].Cas,An[KPravy].SPos);
if (KLevy != 0) {
if (An[KLevy-1].Dir == +1) {
Kolize[KSize++]=KLevy-1;
//printf("AddL %d\n",KLevy-1);
};
};
if (KPravy < A-1) {
if (An[KPravy+1].Dir == -1) {
Kolize[KSize++]=KPravy;
//printf("AddR %d\n",KPravy);
};
};
};
for (i=0;i<A;i++) if (An[i].Dir == -1) {
An[i].FallT = An[i].Pos + An[i].Cas;
} else {
An[i].FallT = L*2 - An[i].Pos + An[i].Cas;
};
Max = -1;
for (i=0;i<A;i++) if (An[i].FallT > Max) Max = An[i].FallT;
printf("The last ant will fall down in %d seconds - started at ",Max/2);
MaxF = 0;
for (i=0;i<A;i++) {
if (An[i].FallT == Max) {
if (MaxF == 1) printf(" and ");
printf("%d",An[i].SPos);
MaxF = 1;
};
};
printf(".\n");
};
return 0;
};