Source code for submission s1116

Go to diff to previous submission

a.cpp

  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cctype>
  6. #include <string>
  7. #include <cstring>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <utility>
  11. #include <stack>
  12. #include <vector>
  13. #include <queue>
  14. #include <deque>
  15. #include <set>
  16. #include <map>
  17. #include <list>
  18.  
  19. #define SIZEOF(a) (sizeof(a)/sizeof(a[0]))
  20. #define FILL(a,b) fill(a,a+SIZEOF(a),b)
  21. #define FOR(a,b,c) for(int a=b;a<=c;a++)
  22. #define DOWNFOR(a,b,c) for(int a=b;a>=c;a--)
  23. #define FORARR(i,a) for(unsigned i=0; i<SIZEOF(a); i++)
  24. #define FOREACH(a,b) for(__typeof((b).begin()) a = (b).begin(); a!=(b).end(); a++)
  25. #define GETI(a) scanf("%d ", &a);
  26. #define SWAP(a,b) { __typeof(a) t = a; a = t; b = t; }
  27.  
  28. using namespace std;
  29.  
  30.  
  31. struct ant {
  32. int id;
  33. int pos;
  34. int dir; // 1 for right, -1 for left
  35. ant(int id, int pos, int dir) : id(id), pos(pos), dir(dir) {}
  36. };
  37.  
  38. bool operator<(const ant& a, const ant& b) {
  39. return a.pos < b.pos;
  40. }
  41.  
  42. void answer(int id, int time)
  43. {
  44. cout << "The last ant will fall down in " << time << " seconds - started at " << id << "." << endl;
  45. }
  46.  
  47. void answer(int id, int id2, int time)
  48. {
  49. cout << "The last ant will fall down in " << time << " seconds - started at " << id << " and " << id2 << "." << endl;
  50. }
  51.  
  52.  
  53. void print_ants(deque<ant> ants)
  54. {
  55. FOREACH(a,ants) {
  56. cerr << a->id << "(pos " << a->pos << ", dir " << a->dir << "), ";
  57. }
  58. }
  59.  
  60.  
  61.  
  62. int main(void)
  63. {
  64. int L, A;
  65. GETI(L); GETI(A);
  66. while (!feof(stdin)) {
  67. // cerr << "-----------------------------" << endl;
  68. // cerr << "read " << L << " " << A << endl;
  69.  
  70. vector<ant> antsv;
  71. FOR(i,1,A) {
  72. int pos;
  73. char dir;
  74. GETI(pos);
  75. scanf("%c ", &dir);
  76. antsv.push_back(ant(pos, pos, (dir == 'L' ? -1 : 1)));
  77. }
  78.  
  79. // sort by pos
  80. sort(antsv.begin(), antsv.end());
  81.  
  82. int time = 0;
  83. int firstToRight, firstToLeft;
  84. FOR(i,0,A-1) {
  85. if (antsv[i].dir == 1) {
  86. time = max(time, L - antsv[i].pos);
  87. firstToRight = i;
  88. break;
  89. }
  90. }
  91. DOWNFOR(i,A-1,0) {
  92. if (antsv[i].dir == -1) {
  93. time = max(time, antsv[i].pos);
  94. firstToLeft = i;
  95. break;
  96. }
  97. }
  98.  
  99.  
  100. // count dir to the right
  101. int rightistsSoFar = 0;
  102. int leftistsSoFar = 0;
  103. vector<int> rightists(A); // rightists[i] = pocet mravencu nalevo od i kteri jdou vpravo
  104. vector<int> leftists(A); // leftists[i] = pocet mravencu napravo od i kteri jdou vlevo
  105. FOR(i,0,A-1) {
  106. rightists[i] = rightistsSoFar;
  107. if (antsv[i].dir == 1) {
  108. rightistsSoFar++;
  109. }
  110. }
  111. DOWNFOR(i,A-1,0) {
  112. leftists[i] = leftistsSoFar;
  113. if (antsv[i].dir == -1) {
  114. leftistsSoFar++;
  115. }
  116. }
  117.  
  118. // FOR(i,0,A-1) {
  119. // cerr << "ant " << i << ": leftists = " << leftists[i] << ", rightists = " << rightists[i] << endl;
  120. // }
  121.  
  122.  
  123. // find the last fallers
  124. int fallerToRight = -1;
  125. FOR(i,0,A-1) {
  126. if (rightists[i]+max(0,antsv[i].dir) > leftists[i]) {
  127. fallerToRight = i;
  128. break;
  129. }
  130. }
  131. int fallerToLeft = -1;
  132. DOWNFOR(i,A-1,0) {
  133. if (leftists[i]-min(0, antsv[i].dir) > rightists[i]) {
  134. fallerToLeft = i;
  135. break;
  136. }
  137. }
  138.  
  139. // cerr<<"fallers: "<<fallerToRight<<" "<<fallerToLeft<<endl;
  140. // cerr << "first to right: " << firstToRight << ", left: " << firstToLeft << endl;
  141.  
  142.  
  143. if (fallerToRight == -1) {
  144. answer(antsv[fallerToLeft].id, time);
  145. }
  146. else if (fallerToLeft == -1) {
  147. answer(antsv[fallerToRight].id, time);
  148. }
  149. else {
  150. // TODO
  151. int lastCrashMul2 = (antsv[firstToRight].pos + antsv[firstToLeft].pos);
  152. if (lastCrashMul2 == L) {
  153. // both
  154. answer(min(antsv[fallerToRight].id, antsv[fallerToLeft].id), max(antsv[fallerToRight].id, antsv[fallerToLeft].id), time);
  155. }
  156. else if (lastCrashMul2 < L) {
  157. // faller to right
  158. answer(antsv[fallerToRight].id, time);
  159. }
  160. else {
  161. answer(antsv[fallerToLeft].id, time);
  162. }
  163.  
  164.  
  165.  
  166. /*
  167. // ten kdo je dal od kraje, ze ktereho spadne
  168. int ftrDist = L-antsv[fallerToRight].pos;
  169. int ftlDist = antsv[fallerToLeft].pos;
  170. if (ftrDist == ftlDist) {
  171. answer(min(antsv[fallerToRight].id, antsv[fallerToLeft].id), max(antsv[fallerToRight].id, antsv[fallerToLeft].id), time);
  172. }
  173. else if (ftrDist > ftlDist) {
  174. answer(antsv[fallerToRight].id, time);
  175. }
  176. else {
  177. answer(antsv[fallerToLeft].id, time);
  178. }
  179. */
  180. }
  181.  
  182.  
  183.  
  184. GETI(L); GETI(A);
  185. }
  186.  
  187.  
  188.  
  189. return 0;
  190. }
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228. int _main(void)
  229. {
  230. int L, A;
  231. GETI(L); GETI(A);
  232. while (!feof(stdin)) {
  233. L *= 2;
  234. // cerr << "read " << L << " " << A << endl;
  235.  
  236. deque<ant> ants;
  237. vector<ant> antsv;
  238. FOR(i,1,A) {
  239. int pos;
  240. char dir;
  241. GETI(pos);
  242. scanf("%c ", &dir);
  243. antsv.push_back(ant(pos, pos*2, (dir == 'L' ? -1 : 1)));
  244. }
  245.  
  246. // sort by pos
  247. sort(antsv.begin(), antsv.end());
  248.  
  249. FOREACH(a, antsv) {
  250. ants.push_back(*a);
  251. }
  252. // print_ants(ants);
  253. // cerr << endl;
  254.  
  255. FOR(time,0,L+3) {
  256. // cerr << "AT " << time << ": ";
  257. // print_ants(ants);
  258. // cerr << endl;
  259.  
  260.  
  261. // let them walk
  262. FOREACH(i,ants) {
  263. // collsions?
  264. deque<ant>::iterator nb = i+1;
  265. if (nb != ants.end() && nb->pos == i->pos) {
  266. i->dir *= -1;
  267. nb->dir *= -1;
  268. if (i->pos == nb->pos) {
  269. i->pos += i->dir;
  270. nb->pos += nb->dir;
  271. }
  272. i++;
  273. }
  274. else {
  275. i->pos += i->dir;
  276. }
  277. }
  278.  
  279. // let them fall
  280. int fallenId = -1;
  281. if (ants.front().pos == -1) {
  282. fallenId = ants.front().id;
  283. if (ants.size() == 1) {
  284. answer(fallenId, time/2);
  285. break;
  286. }
  287. ants.pop_front();
  288. }
  289. if (ants.back().pos == L+1) {
  290. if (ants.size() == 1) {
  291. // the last ant!
  292. int id = ants.back().id;
  293. if (fallenId == -1) {
  294. // id is the only one
  295. answer(id, time/2);
  296. }
  297. else {
  298. // they both fell down now
  299. answer(min(fallenId, id), max(fallenId, id), time/2);
  300. }
  301. break; // we won!
  302. }
  303.  
  304. ants.pop_back();
  305. }
  306. }
  307.  
  308.  
  309. GETI(L); GETI(A);
  310. }
  311.  
  312.  
  313.  
  314. return 0;
  315. }
  316.  

Diff to submission s1030

a.cpp

--- 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);
         }
+        */
       }