제출 #43093

#제출 시각아이디문제언어결과실행 시간메모리
43093RayaBurong25_1커다란 상품 (IOI17_prize)C++14
0 / 100
1000 ms3584 KiB
#include "prize.h" #include <stdio.h> #include <vector> #include <algorithm> int L[200005], R[200005]; std::vector<int> V; std::vector<int> W; int min(int a, int b) { return (a < b)?a:b; } int max(int a, int b) { return (a > b)?a:b; } int find_best(int n) { int i; for (i = 0; i < n; i++) L[i] = -1; int sqrtn; for (sqrtn = 1; sqrtn*sqrtn < n; sqrtn++); // printf("sqrtn %d\n", sqrtn); std::vector<int> r; for (i = 0; i*sqrtn < n; i++) { r = ask(i*sqrtn); L[i*sqrtn] = r[0]; R[i*sqrtn] = r[1]; V.push_back(-r[1]); W.insert(W.begin(), -r[0]); } int sig = 0; int mn, md, mx; //find first sig mn = 0; mx = n - 1; while (mn != mx) { if (mx - mn == 1) { sig = mx; break; } md = (mn + mx)/2; if (L[md] == -1) { r = ask(md); L[md] = r[0]; R[md] = r[1]; } if (R[md] >= R[sig]) mn = md; else mx = md; } if (mn == mx) sig = mn; if (L[sig] == -1) { r = ask(sig); L[sig] = r[0]; R[sig] = r[1]; } int ssig = sig; //go right while (L[sig] != 0 || R[sig] != 0) { // printf("sig %d\n", sig); mx = std::lower_bound(V.begin() + sig/sqrtn + 1, V.end(), -R[sig]) - V.begin(); mx *= sqrtn; mx = min(mx, n - 1); mn = mx - sqrtn; mn = max(mn, sig); // printf("sig %d mn %d mx %d\n", sig, mn, mx); while (mn != mx) { if (mx - mn == 1) { sig = mx; break; } md = (mn + mx)/2; if (L[md] == -1) { r = ask(md); L[md] = r[0]; R[md] = r[1]; } if (R[md] > R[sig]) mn = md; else mx = md; } if (mn == mx) sig = mn; if (L[sig] == -1) { r = ask(sig); L[sig] = r[0]; R[sig] = r[1]; } if (sig == n - 1 && (L[sig] != 0 || R[sig] != 0)) break; } if (sig == n - 1 && (L[sig] != 0 || R[sig] != 0)) { sig = ssig; while (L[sig] != 0 || R[sig] != 0) { // printf("sig %d\n", sig); mn = W.end() - 1 - std::lower_bound(W.end() - 1 - sig/sqrtn, W.end(), -L[sig]); mn *= sqrtn; mn = max(mx, 0); mx = mn + sqrtn; mx = min(mx, sig); // printf("sig %d mn %d mx %d\n", sig, mn, mx); while (mn != mx) { if (mx - mn == 1) { sig = mn; break; } md = (mn + mx)/2; if (L[md] == -1) { r = ask(md); L[md] = r[0]; R[md] = r[1]; } if (L[md] > L[sig]) mx = md; else mn = md; } if (mn == mx) sig = mn; if (L[sig] == -1) { r = ask(sig); L[sig] = r[0]; R[sig] = r[1]; } } return sig; } else return sig; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...