Submission #103742

#TimeUsernameProblemLanguageResultExecution timeMemory
103742alexpetrescuRail (IOI14_rail)C++14
30 / 100
3036 ms263168 KiB
#include "rail.h" #include <algorithm> #include <set> #include <cstdio> #define INF 1000000000 #define MAXN 5009 int dist[MAXN], perm[MAXN]; std::set < int > C, D; std::set < int > ::iterator it, it2; bool cmp(const int &a, const int &b) { return dist[a] < dist[b]; } inline bool notFound(int x) { it = C.lower_bound(x); if (it != C.end() && *it == x) return 0; it = D.lower_bound(x); if (it != D.end() && *it == x) return 0; return 1; } inline int myGetDistance(int x, char a, int y, char b) { if (a == 'C') { if (b == 'D') { if (x < y) return y - x; it = D.lower_bound(x); if (it == D.end()) return INF; it2 = C.lower_bound(y); if (it2 == C.begin()) return INF; it2--; return *it - x + *it - *it2 + y - *it2; } else { it = D.lower_bound(std::max(x, y)); if (it == D.end()) return INF; return *it - x + *it - y; } } else if (b == 'C') { if (x > y) return x - y; it = C.lower_bound(x); if (it == C.begin()) return INF; it--; it2 = D.lower_bound(y); if (it2 == D.end()) return INF; return x - *it + *it2 - *it + *it2 - y; } else { it = C.lower_bound(std::min(x, y)); if (it == C.begin()) return INF; it--; return x - *it + y - *it; } } inline void solve(int x, int first, int &val, int &tip, int &left, int &right) { it = D.end(); it--; int A = *it, B = *(C.begin()); int dA = getDistance(x, right), dB = getDistance(x, left); int d = B + dB, c = A - dA; bool okD = (notFound(d) && myGetDistance(A, 'D', d, 'D') == dA && myGetDistance(first, 'C', d, 'D') == dist[x]); bool okC = (notFound(c) && myGetDistance(B, 'C', c, 'C') == dB && myGetDistance(first, 'C', c, 'C') == dist[x]); if (okD == 0 && okC == 0) while(1) printf("no solution\n"); /*else if (okD && okC) while(1) printf("confused\n");*/ if (okD) { val = d; tip = 2; D.insert(val); it = D.upper_bound(val); if (it == D.end()) right = x; } else { val = c; tip = 1; C.insert(val); it = C.lower_bound(val); if (it == C.begin()) left = x; } } void findLocation(int N, int first, int location[], int stype[]) { location[0] = first; stype[0] = 1; for (int i = 1; i < N; i++) { dist[i] = getDistance(0, i); perm[i] = i; } std::sort(perm + 1, perm + N, cmp); location[perm[1]] = first + dist[perm[1]]; stype[perm[1]] = 2; C.insert(first); D.insert(location[perm[1]]); int left = 0, right = perm[1]; for (int i = 2; i < N; i++) solve(perm[i], first, location[perm[i]], stype[perm[i]], left, right); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...