Go to diff to previous submission
--- c4.s1142.cteam102.ants.cpp.0.ants2.cpp +++ c4.s1234.cteam102.ants.cpp.0.ants.cpp @@ -1,105 +1,89 @@ -#include <cstdio> -#include <cstring> +#include <stdio.h> +#include <algorithm> +#include <string.h> -#include <cstdlib> +#define debug(format,...) fprintf(stderr, format, __VA_ARGS__) +class Ant; +bool operator< (const Ant&, const Ant &); -struct Ant { - int dir; - int start; +class Ant { + public: + int dir; + int id; + int time; + friend bool operator< (const Ant&, const Ant &); +/* bool operator<= (const Ant &ant) { + return this->id <= ant.id; + }*/ + void reverse(Ant *ant) { + std::swap<int>(this->time, ant->time); + this->dir *= -1; + ant->dir *= -1; + } + bool compare(Ant *ant) { + if(this->dir==1 && ant->dir==-1) { + this->reverse(ant); + return true; + } + return false; + } }; -int main() -{ - int ants, pos, woodlen; - char dir; - while(scanf("%d %d", &woodlen, &ants)>0) - { - Ant *wood[woodlen]; - memset (wood,NULL,woodlen*sizeof(Ant*)); +bool operator< (const Ant &ant1, const Ant &ant2) { + return ant1.id < ant2.id; +} + + +int main() { + Ant ant[100000]; + int ants, pos, len, i, j; + int maxTime=-1, maxAnt1=-1, maxAnt2=-1; + char dir[3]; + while(scanf("%d %d", &len, &ants)>0) { + memset(ant, 0, (len+1)*sizeof(Ant)); - for(int i=0; i<ants; i++) - { - scanf("%d %c", &pos, &dir); - Ant *a = new Ant; - if(dir=='R') - a->dir = 1; - else - a->dir = -1; - a->start=pos; - - wood[pos]=a; - printf( "%d\n", a->dir ); + for(i=0; i<ants; i++) { + scanf("%d %s", &pos, dir); + ant[pos].id = pos; + ant[pos].dir = (dir[0]=='L' ? -1 : 1); + ant[pos].time = (ant[pos].dir==-1 ? pos : len-pos); } - - int time=1; - Ant * Lf,*Rf; - while (ants >0) - { - Lf=NULL; - Rf=NULL; - - if(( wood[0] != NULL ) && ( wood[0]->dir==-1))//L - { - Lf=wood[0]; - wood[0]=NULL; - ants--; - - } - - if((wood[woodlen-1]!=NULL)&&(wood[woodlen-1]->dir==1))//P - { - Rf=wood[woodlen-1]; - wood[woodlen-1]=NULL; - ants--; - } - for (int i=1 ; i<woodlen-1; i++) - { - - - if(wood[i]!=NULL) - { - if(wood[i+wood[i]->dir]!=NULL) //jetam - wood[i]->dir*=-1; - else - { - //printf("Dir %d", wood[i]->dir ); - wood[i+wood[i]->dir] = wood[i]; - wood[i]=NULL; - i++; - } - } + for(i=0,j=0; i<=len; i++) { + if(i!=j && ant[i].dir) { + memcpy(ant+j,ant+i, sizeof(Ant)); + j++; } - - time++; - } - if(Rf!=NULL && Lf!=NULL) - { - int a = Rf->start,b = Lf->start; - - if(Rf->start > Lf->start) - { - a=Lf->start; - b=Rf->start; + for(i=0; i<ants-1; i++) { + j=i; + while(ant[j].compare(ant+j+1) && j>0) { + if(j==0) { + break; + } + j--; } - - printf("The last will fall down in %d seconds - started at %d and %d.\n", time,a,b); - } - else - { - if(Rf!=NULL) - { - printf("The last will fall down in %d seconds - started at %d\n", time,Rf->start); - } - else - { - printf("The last will fall down in %d seconds - started at %d\n", time,Lf->start); + maxTime = maxAnt2 = -1; + for(i=0; i<ants; i++) { + if(ant[i].time == maxTime) { + maxAnt2 = ant[i].id; + }else if (ant[i].time > maxTime) { + maxAnt1 = ant[i].id; + maxAnt2 = -1; + maxTime = ant[i].time; } } - + if (maxAnt2 == -1) { + printf( + "The last ant will fall down in %d seconds - started at %d.\n", + maxTime, maxAnt1); + }else { + printf( + "The last ant will fall down in %d seconds - started at %d and %d.\n", + maxTime, maxAnt1, maxAnt2); + } } return 0;