Source code for submission s1246

Go to diff to previous submission

ants.cpp

  1. /*
  2.  * File:   ants.c
  3.  * Author: cteam057
  4.  *
  5.  * Created on October 27, 2012, 12:39 PM
  6.  */
  7.  
  8. #include <cstdlib>
  9. #include <cstdio>
  10.  
  11. /*
  12.  *
  13.  */
  14.  
  15.  
  16. int cycles, l;
  17.  
  18. class Ant {
  19. public:
  20.     double state, pos;
  21.     int start, moved;
  22.     Ant() {
  23.         state = pos = start = moved = 0;
  24.     }
  25.     void operator=(Ant &b) {
  26.         start=b.start;
  27.         pos=b.pos;
  28.         moved=b.moved;
  29.         state=b.state;
  30.     }
  31. };
  32.  
  33. int comp(const void* a, const void* b) {
  34.     Ant* bx = (Ant *)b;
  35.     Ant* ax = (Ant *)a;
  36.     if(ax->start<bx->start) return -1;
  37.     if(ax->start==bx->start) return 0;
  38.     return 1;
  39. }
  40.  
  41.  
  42. int main(int argc, char** argv) {
  43.     int a;
  44.     int i, p, j, mov, st, end, skst, skend;
  45.     char d;
  46.     Ant *ants;
  47.  
  48.     while(scanf("%d %d", &l, &a)==2) {
  49.         ants = new Ant[a];
  50.         cycles=0;
  51.         st=0;
  52.         end=a;
  53.         for(i = 0; i < a; i++) {
  54.             scanf("%d %c", &p, &d);
  55.             ants[i].start=p;
  56.             ants[i].pos=p;
  57.             if(d == 'L') {
  58.                 ants[i].state = -0.5;
  59.                 if(p>cycles) cycles = p;
  60.             } else {
  61.                 ants[i].state = 0.5;
  62.                 if((l-p)>cycles) cycles = l-p;
  63.             };
  64.         }
  65.  
  66.         qsort(ants, a, sizeof(Ant), comp );
  67.  
  68.         i = 0;
  69.         while(i < cycles*2) {
  70.             mov = l;
  71.             skst=0;
  72.             skend=0;
  73.             for(j = st+1; j<end; j++) {
  74.                 if(ants[j].state<0&&ants[j-1].state>0
  75.                         && ants[j].pos-ants[j-1].pos<mov) mov = ants[j].pos-ants[j-1].pos;
  76.             }
  77.             ants[st].pos += ants[st].state*mov;
  78.             if(ants[st].state) ants[st].moved = 1; else ants[0].moved = 0;
  79.             if(ants[st].pos<=0) {ants[st].state=0; skst++;}
  80.             if(ants[st].pos>=l) {ants[st].state=0; skend++;}
  81.  
  82.             for(j = st+1; j < end; j++) {
  83.                 ants[j].pos += ants[j].state*mov;
  84.                 if(ants[j].state) ants[j].moved = 1; else ants[j].moved = 0;
  85.                 if(ants[j].pos==ants[j-1].pos) {
  86.                     ants[j].state*=-1;
  87.                     ants[j-1].state*=-1;
  88.                 }
  89.                 if(ants[j].pos<=0) {ants[j].state=0; skst++;}
  90.                 if(ants[j].pos>=l) {ants[j].state=0; skend++;}
  91.             }
  92.             st+=skst;
  93.             end+=skend;
  94.             i+=mov;
  95.         }
  96.  
  97.         if(cycles==0) {
  98.             if(ants[0].state<0) ants[0].moved=1;
  99.             for(i = 1; i<a-1; i++) {
  100.                 ants[i].moved=0;
  101.             }
  102.             if(ants[a-1].state>0) ants[a-1].moved=1;
  103.         }
  104.  
  105.         printf("The last ant will fall down in %d seconds - started at ", cycles);
  106.         j = 0;
  107.         for(i = ((st>0)?st-1:0); i < ((end<a)?end:a); i++) {
  108.             if(ants[i].moved&&j==0) {
  109.                 j++;
  110.                 printf("%d", ants[i].start);
  111.                 continue;
  112.             }
  113.             if(ants[i].moved&&j==1) {
  114.                 printf(" and %d", ants[i].start);
  115.                 break;
  116.             }
  117.         }
  118.         printf(".\n");
  119.  
  120.         delete[] ants;
  121.     }
  122.     return 0;
  123. }
  124.  
  125.  

Diff to submission s1128

ants.cpp

--- c4.s1128.cteam057.ants.cpp.0.ants.cpp
+++ c4.s1246.cteam057.ants.cpp.0.ants.cpp
@@ -42,5 +42,5 @@
 int main(int argc, char** argv) {
     int a;
-    int i, p, j, mov;
+    int i, p, j, mov, st, end, skst, skend;
     char d;
     Ant *ants;
@@ -49,4 +49,6 @@
         ants = new Ant[a];
         cycles=0;
+        st=0;
+        end=a;
         for(i = 0; i < a; i++) {
             scanf("%d %c", &p, &d);
@@ -67,13 +69,16 @@
         while(i < cycles*2) {
             mov = l;
-            for(j = 1; j<a; j++) {
+            skst=0;
+            skend=0;
+            for(j = st+1; j<end; j++) {
                 if(ants[j].state<0&&ants[j-1].state>0
                         && ants[j].pos-ants[j-1].pos<mov) mov = ants[j].pos-ants[j-1].pos;
             }
+            ants[st].pos += ants[st].state*mov;
+            if(ants[st].state) ants[st].moved = 1; else ants[0].moved = 0;
+            if(ants[st].pos<=0) {ants[st].state=0; skst++;}
+            if(ants[st].pos>=l) {ants[st].state=0; skend++;}
             
-            ants[0].pos += ants[0].state*mov;
-            if(ants[0].state) ants[0].moved = 1; else ants[0].moved = 0;
-            if(ants[0].pos<=0 || ants[0].pos>=l) ants[0].state=0;
-            for(j = 1; j < a; j++) {
+            for(j = st+1; j < end; j++) {
                 ants[j].pos += ants[j].state*mov;
                 if(ants[j].state) ants[j].moved = 1; else ants[j].moved = 0;
@@ -82,6 +87,9 @@
                     ants[j-1].state*=-1;
                 }
-                if(ants[j].pos<=0 || ants[j].pos>=l) ants[j].state=0;
+                if(ants[j].pos<=0) {ants[j].state=0; skst++;}
+                if(ants[j].pos>=l) {ants[j].state=0; skend++;}
             }
+            st+=skst;
+            end+=skend;
             i+=mov;
         }
@@ -97,5 +105,5 @@
         printf("The last ant will fall down in %d seconds - started at ", cycles);
         j = 0;
-        for(i = 0; i < a; i++) {
+        for(i = ((st>0)?st-1:0); i < ((end<a)?end:a); i++) {
             if(ants[i].moved&&j==0) {
                 j++;
@@ -110,5 +118,5 @@
         printf(".\n");
         
-        delete ants;
+        delete[] ants;
     }
     return 0;