Go to diff to previous submission
#include<iostream> #include<vector> #include<algorithm> #include<map> #include<set> #include<list> #include<stack> #include<queue> #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> using namespace std; #define FOR(i,a,b) for(int i=a;i<=b;i++) #define PB push_back #define PII pair<int,int> #define PLL pair<ll,ll> #define MP make_pair #define fi first #define se second #define SIZE(s) (int) (s).size() #define INF 987654321 #define ll long long //---------------------- int N; int dlzka; vector< pair<int, char> > V; vector< pair<int, char> > V2; int find(double val) { FOR(i,0,SIZE(V2)-1) if (V2[i].fi > val) return i; return -1; } void solve2(int lavy, int pravy,int kolko) { int pozL = V2[lavy].fi; int pozR = V2[pravy].fi; if (dlzka-pozR == pozL) printf("The last ant will fall down in %d seconds - started at %d and %d.\n",kolko,pozL,pozR); else if (dlzka-pozR > pozL) printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR); else printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL); } void solve1(int lavy, int pravy,int kolko) { if (lavy == -1) { int pozR = V[pravy].fi; printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR); } else if (pravy == -1) { int pozL = V[lavy].fi; printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL); } else { int pozL = V[lavy].fi; int pozR = V[pravy].fi; if (dlzka-pozR == pozL) printf("The last ant will fall down in %d seconds - started at %d and %d.\n",kolko,pozL,pozR); else if (dlzka-pozR > pozL) printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR); else printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL); } } int main() { char z; int poz; while(scanf("%d %d",&dlzka,&N)==2) { V.clear(); V2.clear(); int kolko=-1; int lavy = -1; int pravy = -1; bool existuje = false; FOR(i,0,N-1) { scanf("%d %c",&poz,&z); //cout << poz << " " << z << endl; if (z == 'L') kolko = max(poz,kolko); else kolko = max(kolko,dlzka-poz); V.PB(MP(poz,z)); } sort(V.begin(),V.end()); FOR(i,0,N-1) { if (i>0 && V[i-1].se == 'L' && V[i].se == 'R') existuje = true; if (V[i].se == 'L') lavy = i; if (pravy == -1 && V[i].se == 'R') pravy = i; } // cout << lavy << endl; FOR(i,0,N-1) { if (pravy == -1 && V[i].se == 'L') { } else V2.PB(V[i]); if (lavy > 0 && lavy == i) break; } if (existuje) { int pozL = V2[0].fi; int pozR = V2[SIZE(V2)-1].fi; // cout << pozL << " " << pozR << endl; double stred = (pozL+pozR) / 2.0; int idx1 = find(stred); // cout << stred << " " << idx1 << endl; int idx2 = idx1-1; solve2(idx2,idx1,kolko); } else { solve1(lavy,pravy,kolko); } } return 0; }