Submission #548252

#TimeUsernameProblemLanguageResultExecution timeMemory
548252sidonRail (IOI14_rail)C++17
30 / 100
80 ms516 KiB
#include <bits/stdc++.h> using namespace std; #include "rail.h" void findLocation(int N, int o, int* x, int* t) { int d[N] {}, byD[N - 1], g[1<<20] {}; t[0] = g[x[0] = o] = 1; for(int v = 1; v < N; ++v) { d[v] = getDistance(0, v); byD[v-1] = v; } sort(byD, byD + N - 1, [&](const int &i, const int &j) { return d[i] < d[j]; }); int c = byD[0], rD = c, lD = c, rC {}, lC {}; t[c] = g[x[c] = o + d[c]] = 2; for(const int &v : byD) if(v != c) { int z = getDistance(c, v); if(z > d[v]) { int y = getDistance(rD, v); int exp = x[rD] - x[rC] + (o + d[v]) - x[rC]; if(y == exp) x[rD = v] = o + d[v], t[v] = 2; else x[v] = d[rD] - y, t[v] = 1; } else { int y = getDistance(lC, v); if(!lC) x[lC = v] = x[c] - z, t[v] = 1; else { int exp = x[lD] - x[lC] + x[lD] - (x[c] - z); if(y == exp) x[lC = v] = x[c] - z, t[v] = 1; else x[v] = x[lC] + y, t[v] = 2; } } if(t[v] == 1 && x[v] > x[rC]) rC = v; if(t[v] == 2 && x[v] < x[lD]) lD = v; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...