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; FOR(i,0,A-1) { if (antsv[i].dir == 1) { time = max(time, L - antsv[i].pos); break; } } DOWNFOR(i,A-1,0) { if (antsv[i].dir == -1) { time = max(time, antsv[i].pos); 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; if (fallerToRight == -1) { answer(antsv[fallerToLeft].id, time); } else if (fallerToLeft == -1) { answer(antsv[fallerToRight].id, time); } else { // 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.s838.cteam092.ants.cpp.0.a.cpp +++ c4.s1030.cteam092.ants.cpp.0.a.cpp @@ -20,4 +20,5 @@ #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++) @@ -60,7 +62,147 @@ 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; + FOR(i,0,A-1) { + if (antsv[i].dir == 1) { + time = max(time, L - antsv[i].pos); + break; + } + } + DOWNFOR(i,A-1,0) { + if (antsv[i].dir == -1) { + time = max(time, antsv[i].pos); + 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; + if (fallerToRight == -1) { + answer(antsv[fallerToLeft].id, time); + } + else if (fallerToLeft == -1) { + answer(antsv[fallerToRight].id, time); + } + else { + // 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; - cin >> L >> A; + GETI(L); GETI(A); while (!feof(stdin)) { L *= 2; @@ -72,5 +214,6 @@ int pos; char dir; - cin >> pos >> dir; + GETI(pos); + scanf("%c ", &dir); antsv.push_back(ant(pos, pos*2, (dir == 'L' ? -1 : 1))); } @@ -139,6 +282,5 @@ - - cin >> L >> A; + GETI(L); GETI(A); }