Submission #430356

#TimeUsernameProblemLanguageResultExecution timeMemory
430356Dremix10The Big Prize (IOI17_prize)C++17
20 / 100
117 ms14784 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pi; typedef pair<ll,ll> pl; #define endl '\n' #define F first #define S second #define all(x) (x).begin(),(x).end() const int N = 3e5+1; const ll INF = 2e18; const int MOD = 1e9+7; vector<int> ask(int i); vector<vector<int> > memo(N); const int block = 5; int nn; int queried = 0; vector<int> askme(int i){ if(memo[i].empty()){ queried++; assert(queried <= 10000); memo[i] = ask(i); } return memo[i]; } int seen,cheap; int go(int b){ for(int i=b*block;i<min(nn,(b+1)*block);i++){ vector<int> arr = askme(i); if(arr[0] + arr[1] == 0) return i; if(arr[0] + arr[1] < cheap) seen++; } return -1; } int find_best(int n) { /// the second to smallest price is in at most 450 boxes /// the maximum amount of prizes is 5 nn = n; int blocks = (n+4)/5; for(int i=0;i<min(700,n);i++){ vector<int> arr = askme(i); cheap = max(cheap,arr[0] + arr[1]); } int L = 1,R = blocks-1; while(L<=R){ int l = L,r = R; while(l<=r){ int mid = (l+r)/2; int low,high,pos; pos = mid*block; vector<int> arr = askme(pos); low = arr[0],high = arr[1]; if(low + high == 0) return pos; if(low + high < cheap){ bool chk = 0; if(mid != 0){ vector<int> arr = askme(pos-1); if(arr[0] + arr[1] < cheap || arr[0] - seen > 0) chk = 1; if(arr[0] + arr[1] == 0) return pos-1; } if(chk){ r = mid-1; } else{ r = mid; l = mid+1; } continue; } if(low - seen > 0) r = mid-1; else l = mid+1; } int ans = go(r); if(ans != -1) return ans; L = r+2; } assert(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...