Go to diff to previous submission
#include <stdio.h> #include <algorithm> #include <string.h> #define debug(format,...) fprintf(stderr, format, __VA_ARGS__) class Ant; bool operator< (const Ant&, const Ant &); 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; } }; bool operator< (const Ant &ant1, const Ant &ant2) { return ant1.id < ant2.id; } int main() { int positions[100000]; 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(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); } for(i=0,j=0; i<=len; i++) { if(i!=j && ant[i].dir) { positions[j++]=i; } } for(i=0; i<ants-1; i++) { j=i; while(ant[positions[j]].compare(ant+positions[j+1]) && j>0) { if(j==0) { break; } j--; } } maxTime = maxAnt2 = -1; for(i=0; i<ants; i++) { if(ant[positions[i]].time == maxTime) { maxAnt2 = ant[positions[i]].id; }else if (ant[positions[i]].time > maxTime) { maxAnt1 = ant[positions[i]].id; maxAnt2 = -1; maxTime = ant[positions[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; }
--- c4.s1234.cteam102.ants.cpp.0.ants.cpp +++ c4.s1279.cteam102.ants.cpp.0.ants.cpp @@ -36,4 +36,5 @@ int main() { + int positions[100000]; Ant ant[100000]; int ants, pos, len, i, j; @@ -52,6 +53,5 @@ for(i=0,j=0; i<=len; i++) { if(i!=j && ant[i].dir) { - memcpy(ant+j,ant+i, sizeof(Ant)); - j++; + positions[j++]=i; } } @@ -59,5 +59,5 @@ for(i=0; i<ants-1; i++) { j=i; - while(ant[j].compare(ant+j+1) && j>0) { + while(ant[positions[j]].compare(ant+positions[j+1]) && j>0) { if(j==0) { break; @@ -69,10 +69,10 @@ 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; + if(ant[positions[i]].time == maxTime) { + maxAnt2 = ant[positions[i]].id; + }else if (ant[positions[i]].time > maxTime) { + maxAnt1 = ant[positions[i]].id; maxAnt2 = -1; - maxTime = ant[i].time; + maxTime = ant[positions[i]].time; } }