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