# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
916370 | 2024-01-25T18:35:31 Z | biank | Rail (IOI14_rail) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; #define ALL(x) x.begin(),x.end() #define forn(i,n) for(int i=0;i<int(n);i++) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define fst first #define snd second typedef pair<int,int> ii; int getDistance(int i, int j); const int C = 1, D = 2; void findLocation(int n, int first, int loc[], int stype[]) { vector<ii> p(n); forsn(i,1,n) p[i]={getDistance(0,i),i}; sort(ALL(p)); set<ii> Cs, Ds; for(auto [d0,i]:p) { if(Cs.empty()) { loc[i]=first; stype[i]=C; Cs.insert((ii){loc[i],i}); continue; } int minC = Cs.begin()->snd; if(Ds.empty()) { loc[i]=loc[minC]+d0; stype[i]=D; Ds.insert((ii){loc[i],i}); continue; } int maxD = Ds.rbegin()->snd; int distItoC = getDistance(i,minC); int distItoD = getDistance(maxD,i); loc[i] = loc[minC] + distItoC; int target = (loc[i] + loc[maxD] - distItoD)/2; auto it = Cs.lower_bound((ii){target,0}); if(it != Cs.end() && loc[i] - it->fst + loc[maxD] - it->fst == distItoD) { stype[i] = D; Ds.insert((ii){loc[i],i}); continue; } loc[i] = loc[maxD] - distItoD; target = (distItoC + loc[i] + loc[minC])/2; it = Ds.lower_bound((ii){target,0}); if(it != Ds.end() && it->fst - loc[i] + it->fst - loc[minC] == distItoC) { stype[i] = C; Cs.insert((ii){loc[i],i}); continue; } assert(false); } }