제출 #615802

#제출 시각아이디문제언어결과실행 시간메모리
615802IvanJ커다란 상품 (IOI17_prize)C++17
20 / 100
44 ms5212 KiB
#include<bits/stdc++.h> #include "prize.h" #define pb push_back #define x first #define y second using namespace std; typedef pair<int, int> ii; const int maxn = 2e5 + 5; vector<int> A[maxn]; vector<int> V; int F = -1; void check(int x) { if(A[x][0] + A[x][1] == 0) F = x; } void find(int L, int R) { int lo = L, hi = R - 1; while(lo <= hi) { int mid = (lo + hi) / 2; if(A[mid].size() == 0) A[mid] = ask(mid); check(mid); if(F != -1) return; if(A[mid][0] + A[mid][1] < A[hi + 1][0] + A[hi + 1][1]) {V.pb(mid);return;} if(A[mid][1] == A[hi + 1][1]) hi = mid - 1; else lo = mid + 1; } } void solve(int lo, int hi, int R) { if(lo >= hi) return; if(R == 0) return; if(R == 1) {find(lo, hi);return;} int mid = (lo + hi) / 2; int mid1 = mid; while(1) { if(A[mid1].size() == 0) A[mid1] = ask(mid1); check(mid); if(F != -1) return; if(A[mid1][0] + A[mid1][1] < A[hi][0] + A[hi][1]) V.pb(mid1), mid1--; else break; if(mid1 < lo) break; } int R1, R2; if(mid1 == -1) R2 = R - (mid - mid1); else R2 = A[mid1][1] - A[hi][1] - (mid - mid1); R1 = R - R2; solve(lo, mid1, R1); solve(mid + 1, hi, R2); } int find_best(int n) { if(n <= 5000) { for(int i = 0;i < n;i++) { A[i] = ask(i); if(A[i][0] + A[i][1] == 0) return i; } } int pos = -1; int s = 460; for(int i = n - 1;i >= n - s;i--) { A[i] = ask(i); check(i); if(F != -1) return F; if(pos == -1 || A[i][0] + A[i][1] > A[pos][0] + A[pos][1]) pos = i; } for(int i = pos + 1;i < n;i++) V.pb(i); solve(0, pos, A[pos][0]); return F; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...