제출 #104277

#제출 시각아이디문제언어결과실행 시간메모리
104277naoai철로 (IOI14_rail)C++14
30 / 100
80 ms792 KiB
#include "rail.h" #include <bits/stdc++.h> using namespace std; const int nmax = 5000; static int v[nmax + 1]; static int tip[nmax + 1]; int d0[nmax + 1]; pair<int, int> ord[nmax + 1]; set<int> C, D; bool checkC (int pos, int L, int dL, int ind) { set<int>::iterator it = D.upper_bound(max(v[0], pos)); if (it == D.end()) return 0; if (d0[ind] != *it * 2 - v[0] - pos) return 0; it = D.upper_bound(max(v[0], v[L])); if (it == D.end()) return 0; return (dL == *it * 2 - v[L] - pos); } bool checkD (int pos, int R, int dR, int ind) { set<int>::iterator it = C.lower_bound(pos); if (it == C.begin()) return 0; -- it; if (dR != pos + v[R] - 2 * (*it)) return 0; set<int>::iterator shp = D.upper_bound(v[0]); if (shp == D.end()) return 0; return (d0[ind] == (*shp - v[0]) + (pos - *it)); } bool checkL (int pos, int dr, int dzero) { set<int>::iterator it = D.lower_bound(v[0]); if (it == D.end()) return 0; if (dzero != 2 * (*it) - v[0] - pos) return 0; return 1; } void findLocation(int N, int first, int location[], int stype[]) { v[0] = first; tip[0] = 1; for (int i = 1; i < N; ++ i) { int x; x = getDistance(0, i); d0[i] = x; ord[i] = {d0[i], i}; } sort(ord + 1, ord + N); int l = 0, r = ord[1].second; v[r] = v[0] + d0[r]; tip[r] = 2; C.insert(v[0]); D.insert(v[r]); for (int i = 2; i < N; ++ i) { int c = ord[i].second; int dl = getDistance(c, l), dr = getDistance(c, r); if (v[0] < v[r] - dr && checkC(v[r] - dr, l, dl, c)) { tip[c] = 1; v[c] = v[r] - dr; C.insert(v[c]); } else if (v[l] + dl < v[0] && checkD(v[l] + dl, r, dr, c)){ tip[c] = 2; v[c] = v[l] + dl; D.insert(v[c]); } else if (v[r] - dr < v[l] && checkL(v[r] - dr, dr, d0[c])) { tip[c] = 1; v[c] = v[r] - dr; C.insert(v[c]); } else { tip[c] = 2; v[c] = v[l] + dl; D.insert(v[c]); } if (v[c] > v[r]) r = c; if (v[c] < v[l]) l = c; } for (int i = 0; i < N; ++ i) { location[i] = v[i]; stype[i] = tip[i]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...