Source code for submission s1182

Go to diff to previous submission

//
// File:   ants.cc
// Author: cteam053
//
// Created on October 27, 2012, 1:06 PM
//
 
#include <stdlib.h>
#include <cstdio>
#include <cmath>
#include <climits>
#include <iostream>
 
using namespace std;
 
int rightAr[100000];
int leftAr[100000];
char ants[100000];
int lCnt = 0;
int rCnt = 0;
int L, A;
int pos;
int maxVal;
int minVal;
int minCnt;
int minAnts[100000];
int r, l;
bool cross;
int dist[100000];
int distFromMid[100000];
int minDist;
int minMidDist;
int resCnt;
int result[10];
 
int main(int argc, char** argv) {
 
    char c, space;
    int len;
    int tmp;
    while(scanf("%d%d", &L, &A) == 2){
        lCnt = 0;
        rCnt = 0;
        minVal = INT_MAX;
        maxVal = -1;
        r = 0;
        l = 0;
        minMidDist = INT_MAX;
        minDist = INT_MAX;
        cross = false;
        for(int i = 0; i < L; i++){
            ants[i] = 'A';
            rightAr[i] = 0;
            leftAr[i] = 0;
        }
        for(int i = 0; i < A; i++){
            scanf("%d%c%c", &pos, &space, &c);
            if(c == 'R'){
                len = L - pos;
            } else {
                len = pos;
            }
            dist[pos] = len;
            distFromMid[pos] = abs(L / 2 - pos);
            maxVal = (maxVal < len) ? len : maxVal;
            ants[pos] = c;
        }
        for(int i = 0; i < L; i++){
            if(ants[i] == 'R'){
                if(i < L - 1)
                    rightAr[i+1] = ++rCnt;
            }
        }
        for(int i = L -1; i > 0; i--){
            if(ants[i] == 'L'){
                leftAr[i-1] = ++lCnt;
            }
        }
 
        for(int i = 0; i < L; i++){
            if(rightAr[i] < r){
                rightAr[i] = r;
            } else if(rightAr[i] > r){
                r = rightAr[i];
            }
        }
        for(int i = L -1; i >= 0; i--){
            if(leftAr[i] < l){
                leftAr[i] = l;
            } else if(leftAr[i] > l){
                l = leftAr[i];
            }
        }
        for(int i = 0; i < L; i++){
            if(rightAr[i] > 0 && leftAr[i] > 0){
                cross = true;
                break;
            }
        }
        if(cross){
            for(int i = 0; i < L; i++){
                if(ants[i] != 'A'){
                    tmp = abs(rightAr[i] - leftAr[i]);
                    if(tmp < minVal){
                        minVal = tmp;
                        minCnt = 0;
                        minAnts[minCnt++] = i;
                    } else if(tmp == minVal){
                        minAnts[minCnt++] = i;
                    }
                }
            }
            for(int i = 0; i < minCnt; i++){
                if(distFromMid[minAnts[i]] < minMidDist){
                    minMidDist = distFromMid[minAnts[i]];
                    minDist = dist[minAnts[i]];
                } else if(distFromMid[minAnts[i]] == minMidDist){
                    if(dist[minAnts[i]] < minDist){
                        minDist = dist[minAnts[i]];
                    }
                }
            }
            resCnt = 0;
            for(int i = 0; i < minCnt; i++){
                if(minMidDist == distFromMid[minAnts[i]]){
                    if(minDist == dist[minAnts[i]]){
                        result[resCnt++] = minAnts[i];
                    }
                }
            }
            printf("The last ant will fall down in %d  seconds - started at ", maxVal);
            for(int i = 0; i < resCnt; i++){
                printf("%d", result[i]);
                if(i == resCnt - 1){
                    printf(".\n");
                } else {
                    printf(" and ");
                }
            }
        } else {
            for(int i = 0; i < L; i++){
                if(dist[i] == maxVal){
                    printf("The last ant will fall down in %d  seconds - started at %d.\n", maxVal, i);
                    break;
                }
            }
        }
    }
 
    return (0);
}
 
 

Diff to submission s1058

--- c4.s1058.cteam053.ants.cpp.0.ants.cpp
+++ c4.s1182.cteam053.ants.cpp.0.ants.cpp
@@ -26,4 +26,11 @@
 int minAnts[100000];
 int r, l;
+bool cross;
+int dist[100000];
+int distFromMid[100000];
+int minDist;
+int minMidDist;
+int resCnt;
+int result[10];
 
 int main(int argc, char** argv) {
@@ -39,4 +46,7 @@
         r = 0;
         l = 0;
+        minMidDist = INT_MAX;
+        minDist = INT_MAX;
+        cross = false;
         for(int i = 0; i < L; i++){
             ants[i] = 'A';
@@ -51,4 +61,6 @@
                 len = pos;
             }
+            dist[pos] = len;
+            distFromMid[pos] = abs(L / 2 - pos);
             maxVal = (maxVal < len) ? len : maxVal;
             ants[pos] = c;
@@ -81,22 +93,55 @@
         }
         for(int i = 0; i < L; i++){
-            if(ants[i] != 'A'){
-                tmp = abs(rightAr[i] - leftAr[i]);
-                if(tmp < minVal){
-                    minVal = tmp;
-                    minCnt = 0;
-                    minAnts[minCnt++] = i;
-                } else if(tmp == minVal){
-                    minAnts[minCnt++] = i;
-                }
+            if(rightAr[i] > 0 && leftAr[i] > 0){
+                cross = true;
+                break;
             }
         }
-        printf("The last ant will fall down in %d  seconds - started at ", maxVal);
-        for(int i = 0; i < minCnt; i++){
-            printf("%d", minAnts[i]);
-            if(i == minCnt - 1){
-                printf(".\n");
-            } else {
-                printf(" and ");
+        if(cross){
+            for(int i = 0; i < L; i++){
+                if(ants[i] != 'A'){
+                    tmp = abs(rightAr[i] - leftAr[i]);
+                    if(tmp < minVal){
+                        minVal = tmp;
+                        minCnt = 0;
+                        minAnts[minCnt++] = i;
+                    } else if(tmp == minVal){
+                        minAnts[minCnt++] = i;
+                    }
+                }
+            }
+            for(int i = 0; i < minCnt; i++){
+                if(distFromMid[minAnts[i]] < minMidDist){
+                    minMidDist = distFromMid[minAnts[i]];
+                    minDist = dist[minAnts[i]];
+                } else if(distFromMid[minAnts[i]] == minMidDist){
+                    if(dist[minAnts[i]] < minDist){
+                        minDist = dist[minAnts[i]];
+                    }
+                }
+            }
+            resCnt = 0;
+            for(int i = 0; i < minCnt; i++){
+                if(minMidDist == distFromMid[minAnts[i]]){
+                    if(minDist == dist[minAnts[i]]){
+                        result[resCnt++] = minAnts[i];
+                    }
+                }
+            }
+            printf("The last ant will fall down in %d  seconds - started at ", maxVal);
+            for(int i = 0; i < resCnt; i++){
+                printf("%d", result[i]);
+                if(i == resCnt - 1){
+                    printf(".\n");
+                } else {
+                    printf(" and ");
+                }
+            }
+        } else {
+            for(int i = 0; i < L; i++){
+                if(dist[i] == maxVal){
+                    printf("The last ant will fall down in %d  seconds - started at %d.\n", maxVal, i);
+                    break;
+                }
             }
         }