Source code for submission s1030

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.       FOR(i,0,A-1) {
  84. 	if (antsv[i].dir == 1) {
  85. 	  time = max(time, L - antsv[i].pos);
  86. 	  break;
  87. 	}
  88.       }
  89.       DOWNFOR(i,A-1,0) {
  90. 	if (antsv[i].dir == -1) {
  91. 	  time = max(time, antsv[i].pos);
  92. 	  break;
  93. 	}
  94.       }
  95.  
  96.  
  97.       // count dir to the right
  98.       int rightistsSoFar = 0;
  99.       int leftistsSoFar = 0;
  100.       vector<int> rightists(A); // rightists[i] = pocet mravencu nalevo od i kteri jdou vpravo
  101.       vector<int> leftists(A); // leftists[i] = pocet mravencu napravo od i kteri jdou vlevo
  102.       FOR(i,0,A-1) {
  103. 	rightists[i] = rightistsSoFar;
  104. 	if (antsv[i].dir == 1) {
  105. 	  rightistsSoFar++;
  106. 	}
  107.       }
  108.       DOWNFOR(i,A-1,0) {
  109. 	leftists[i] = leftistsSoFar;
  110. 	if (antsv[i].dir == -1) {
  111. 	  leftistsSoFar++;
  112. 	}
  113.       }
  114.  
  115. //       FOR(i,0,A-1) {
  116. // 	cerr << "ant " << i << ": leftists = " << leftists[i] << ", rightists = " << rightists[i] << endl;
  117. //       }
  118.  
  119.  
  120.       // find the last fallers
  121.       int fallerToRight = -1;
  122.       FOR(i,0,A-1) {
  123. 	if (rightists[i]+max(0,antsv[i].dir) > leftists[i]) {
  124. 	  fallerToRight = i;
  125. 	  break;
  126. 	}
  127.       }
  128.       int fallerToLeft = -1;
  129.       DOWNFOR(i,A-1,0) {
  130. 	if (leftists[i]-min(0, antsv[i].dir) > rightists[i]) {
  131. 	  fallerToLeft = i;
  132. 	  break;
  133. 	}
  134.       }
  135. //       cerr<<"fallers: "<<fallerToRight<<" "<<fallerToLeft<<endl;
  136.       if (fallerToRight == -1) {
  137. 	answer(antsv[fallerToLeft].id, time);
  138.       }
  139.       else if (fallerToLeft == -1) {
  140. 	answer(antsv[fallerToRight].id, time);
  141.       }
  142.       else {
  143. 	// ten kdo je dal od kraje, ze ktereho spadne
  144. 	int ftrDist = L-antsv[fallerToRight].pos;
  145. 	int ftlDist = antsv[fallerToLeft].pos;
  146. 	if (ftrDist == ftlDist) {
  147. 	  answer(min(antsv[fallerToRight].id, antsv[fallerToLeft].id), max(antsv[fallerToRight].id, antsv[fallerToLeft].id), time);
  148. 	}
  149. 	else if (ftrDist > ftlDist) {
  150. 	  answer(antsv[fallerToRight].id, time);
  151. 	}
  152. 	else {
  153. 	  answer(antsv[fallerToLeft].id, time);
  154. 	}
  155.       }
  156.  
  157.  
  158.  
  159.       GETI(L); GETI(A);
  160.     }
  161.  
  162.  
  163.  
  164.     return 0;
  165. }
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203. int _main(void)
  204. {
  205.     int L, A;
  206.     GETI(L); GETI(A);
  207.     while (!feof(stdin)) {
  208.       L *= 2;
  209. //       cerr << "read " << L << " " << A << endl;
  210.  
  211.       deque<ant> ants;
  212.       vector<ant> antsv;
  213.       FOR(i,1,A) {
  214. 	  int pos;
  215. 	  char dir;
  216. 	  GETI(pos);
  217. 	  scanf("%c ", &dir);
  218. 	  antsv.push_back(ant(pos, pos*2, (dir == 'L' ? -1 : 1)));
  219.       }
  220.  
  221.       // sort by pos
  222.       sort(antsv.begin(), antsv.end());
  223.  
  224.       FOREACH(a, antsv) {
  225. 	ants.push_back(*a);
  226.       }
  227. //       print_ants(ants);
  228. //       cerr << endl;
  229.  
  230.       FOR(time,0,L+3) {
  231. //    	  cerr << "AT " << time << ": ";
  232. //    	  print_ants(ants);
  233. //    	  cerr << endl;
  234.  
  235.  
  236. 	  // let them walk
  237. 	  FOREACH(i,ants) {
  238. 	    // collsions?
  239. 	    deque<ant>::iterator nb = i+1;
  240. 	    if (nb != ants.end() && nb->pos == i->pos) {
  241. 	      i->dir *= -1;
  242. 	      nb->dir *= -1;
  243. 	      if (i->pos == nb->pos) {
  244. 		i->pos += i->dir;
  245. 		nb->pos += nb->dir;
  246. 	      }
  247. 	      i++;
  248. 	    }
  249. 	    else {
  250. 	      i->pos += i->dir;
  251. 	    }
  252. 	  }
  253.  
  254. 	  // let them fall
  255. 	  int fallenId = -1;
  256. 	  if (ants.front().pos == -1) {
  257. 	    fallenId = ants.front().id;
  258. 	    if (ants.size() == 1) {
  259. 	      answer(fallenId, time/2);
  260. 	      break;
  261. 	    }
  262. 	    ants.pop_front();
  263. 	  }
  264. 	  if (ants.back().pos == L+1) {
  265. 	    if (ants.size() == 1) {
  266. 	      // the last ant!
  267. 	      int id = ants.back().id;
  268. 	      if (fallenId == -1) {
  269. 		  // id is the only one
  270. 		  answer(id, time/2);
  271. 	      }
  272. 	      else {
  273. 		  // they both fell down now
  274. 		  answer(min(fallenId, id), max(fallenId, id), time/2);
  275. 	      }
  276. 	      break; // we won!
  277. 	    }
  278.  
  279. 	    ants.pop_back();
  280. 	  }
  281.       }
  282.  
  283.  
  284.       GETI(L); GETI(A);
  285.     }
  286.  
  287.  
  288.  
  289.     return 0;
  290. }
  291.  

Diff to submission s838

a.cpp

--- 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);
     }