Go to diff to previous submission
#include <iostream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cmath> #include <algorithm> #include <utility> #include <stack> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <list> #define SIZEOF(a) (sizeof(a)/sizeof(a[0])) #define FILL(a,b) fill(a,a+SIZEOF(a),b) #define FOR(a,b,c) for(int a=b;a<=c;a++) #define DOWNFOR(a,b,c) for(int a=b;a>=c;a--) #define FORARR(i,a) for(unsigned i=0; i<SIZEOF(a); i++) #define FOREACH(a,b) for(__typeof((b).begin()) a = (b).begin(); a!=(b).end(); a++) #define GETI(a) scanf("%d ", &a); #define SWAP(a,b) { __typeof(a) t = a; a = t; b = t; } using namespace std; struct ant { int id; int pos; int dir; // 1 for right, -1 for left ant(int id, int pos, int dir) : id(id), pos(pos), dir(dir) {} }; bool operator<(const ant& a, const ant& b) { return a.pos < b.pos; } void answer(int id, int time) { cout << "The last ant will fall down in " << time << " seconds - started at " << id << "." << endl; } void answer(int id, int id2, int time) { cout << "The last ant will fall down in " << time << " seconds - started at " << id << " and " << id2 << "." << endl; } void print_ants(deque<ant> ants) { FOREACH(a,ants) { cerr << a->id << "(pos " << a->pos << ", dir " << a->dir << "), "; } } int main(void) { int L, A; GETI(L); GETI(A); while (!feof(stdin)) { // cerr << "-----------------------------" << endl; // cerr << "read " << L << " " << A << endl; vector<ant> antsv; FOR(i,1,A) { int pos; char dir; GETI(pos); scanf("%c ", &dir); antsv.push_back(ant(pos, pos, (dir == 'L' ? -1 : 1))); } // sort by pos sort(antsv.begin(), antsv.end()); int time = 0; int firstToRight, firstToLeft; FOR(i,0,A-1) { if (antsv[i].dir == 1) { time = max(time, L - antsv[i].pos); firstToRight = i; break; } } DOWNFOR(i,A-1,0) { if (antsv[i].dir == -1) { time = max(time, antsv[i].pos); firstToLeft = i; break; } } // count dir to the right int rightistsSoFar = 0; int leftistsSoFar = 0; vector<int> rightists(A); // rightists[i] = pocet mravencu nalevo od i kteri jdou vpravo vector<int> leftists(A); // leftists[i] = pocet mravencu napravo od i kteri jdou vlevo FOR(i,0,A-1) { rightists[i] = rightistsSoFar; if (antsv[i].dir == 1) { rightistsSoFar++; } } DOWNFOR(i,A-1,0) { leftists[i] = leftistsSoFar; if (antsv[i].dir == -1) { leftistsSoFar++; } } // FOR(i,0,A-1) { // cerr << "ant " << i << ": leftists = " << leftists[i] << ", rightists = " << rightists[i] << endl; // } // find the last fallers int fallerToRight = -1; FOR(i,0,A-1) { if (rightists[i]+max(0,antsv[i].dir) > leftists[i]) { fallerToRight = i; break; } } int fallerToLeft = -1; DOWNFOR(i,A-1,0) { if (leftists[i]-min(0, antsv[i].dir) > rightists[i]) { fallerToLeft = i; break; } } // cerr<<"fallers: "<<fallerToRight<<" "<<fallerToLeft<<endl; // cerr << "first to right: " << firstToRight << ", left: " << firstToLeft << endl; if (fallerToRight == -1) { answer(antsv[fallerToLeft].id, time); } else if (fallerToLeft == -1) { answer(antsv[fallerToRight].id, time); } else { // TODO int lastCrashMul2 = (antsv[firstToRight].pos + antsv[firstToLeft].pos); if (lastCrashMul2 == L) { // both answer(min(antsv[fallerToRight].id, antsv[fallerToLeft].id), max(antsv[fallerToRight].id, antsv[fallerToLeft].id), time); } else if (lastCrashMul2 < L) { // faller to right answer(antsv[fallerToRight].id, time); } else { answer(antsv[fallerToLeft].id, time); } /* // ten kdo je dal od kraje, ze ktereho spadne int ftrDist = L-antsv[fallerToRight].pos; int ftlDist = antsv[fallerToLeft].pos; if (ftrDist == ftlDist) { answer(min(antsv[fallerToRight].id, antsv[fallerToLeft].id), max(antsv[fallerToRight].id, antsv[fallerToLeft].id), time); } else if (ftrDist > ftlDist) { answer(antsv[fallerToRight].id, time); } else { answer(antsv[fallerToLeft].id, time); } */ } GETI(L); GETI(A); } return 0; } int _main(void) { int L, A; GETI(L); GETI(A); while (!feof(stdin)) { L *= 2; // cerr << "read " << L << " " << A << endl; deque<ant> ants; vector<ant> antsv; FOR(i,1,A) { int pos; char dir; GETI(pos); scanf("%c ", &dir); antsv.push_back(ant(pos, pos*2, (dir == 'L' ? -1 : 1))); } // sort by pos sort(antsv.begin(), antsv.end()); FOREACH(a, antsv) { ants.push_back(*a); } // print_ants(ants); // cerr << endl; FOR(time,0,L+3) { // cerr << "AT " << time << ": "; // print_ants(ants); // cerr << endl; // let them walk FOREACH(i,ants) { // collsions? deque<ant>::iterator nb = i+1; if (nb != ants.end() && nb->pos == i->pos) { i->dir *= -1; nb->dir *= -1; if (i->pos == nb->pos) { i->pos += i->dir; nb->pos += nb->dir; } i++; } else { i->pos += i->dir; } } // let them fall int fallenId = -1; if (ants.front().pos == -1) { fallenId = ants.front().id; if (ants.size() == 1) { answer(fallenId, time/2); break; } ants.pop_front(); } if (ants.back().pos == L+1) { if (ants.size() == 1) { // the last ant! int id = ants.back().id; if (fallenId == -1) { // id is the only one answer(id, time/2); } else { // they both fell down now answer(min(fallenId, id), max(fallenId, id), time/2); } break; // we won! } ants.pop_back(); } } GETI(L); GETI(A); } return 0; }
--- c4.s1030.cteam092.ants.cpp.0.a.cpp +++ c4.s1116.cteam092.ants.cpp.0.a.cpp @@ -81,7 +81,9 @@ int time = 0; + int firstToRight, firstToLeft; FOR(i,0,A-1) { if (antsv[i].dir == 1) { time = max(time, L - antsv[i].pos); + firstToRight = i; break; } @@ -90,4 +92,5 @@ if (antsv[i].dir == -1) { time = max(time, antsv[i].pos); + firstToLeft = i; break; } @@ -133,5 +136,9 @@ } } + // cerr<<"fallers: "<<fallerToRight<<" "<<fallerToLeft<<endl; +// cerr << "first to right: " << firstToRight << ", left: " << firstToLeft << endl; + + if (fallerToRight == -1) { answer(antsv[fallerToLeft].id, time); @@ -141,4 +148,21 @@ } else { + // TODO + int lastCrashMul2 = (antsv[firstToRight].pos + antsv[firstToLeft].pos); + if (lastCrashMul2 == L) { + // both + answer(min(antsv[fallerToRight].id, antsv[fallerToLeft].id), max(antsv[fallerToRight].id, antsv[fallerToLeft].id), time); + } + else if (lastCrashMul2 < L) { + // faller to right + answer(antsv[fallerToRight].id, time); + } + else { + answer(antsv[fallerToLeft].id, time); + } + + + + /* // ten kdo je dal od kraje, ze ktereho spadne int ftrDist = L-antsv[fallerToRight].pos; @@ -153,4 +177,5 @@ answer(antsv[fallerToLeft].id, time); } + */ }