제출 #112246

#제출 시각아이디문제언어결과실행 시간메모리
112246someone_aa커다란 상품 (IOI17_prize)C++17
0 / 100
7 ms384 KiB
#include "prize.h" #include <bits/stdc++.h> #define P pair<int,int> using namespace std; const int maxn = 200100; bool visited[maxn]; int q[maxn][2]; int max_sum, ind; P query(int i) { if(visited[i]) return {q[i][0], q[i][1]}; visited[i] = true; vector<int>curr = ask(i); q[i][0] = curr[0]; q[i][1] = curr[1]; return {q[i][0], q[i][1]}; } int sum(int i) { query(i); return q[i][0] + q[i][1]; } void solve(int l, int r) { if(l > r || ind != -1) return; P ql = query(l); P qr = query(r); if(ql.first + ql.second == 0) { ind = l; return; } if(qr.first + qr.second == 0) { ind = r; return; } if(ql.first + ql.second != max_sum) { solve(l+1, r); return; } if(qr.first + qr.second != max_sum) { solve(l, r-1); return; } int between = qr.first - ql.first; if(between == 0) return; int mid = (l + r) / 2; solve(l, mid); solve(mid+1, r); } int find_best(int n) { for(int i=0;i<500;i++) { if(sum(i) == 0) return i; max_sum = max(max_sum, sum(i)); } solve(0, n-1); return ind; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...