Submission #39399

#TimeUsernameProblemLanguageResultExecution timeMemory
39399mohammad_kilaniThe Big Prize (IOI17_prize)C++14
100 / 100
69 ms7232 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; const int N = 200010; #define oo 2000000000 bool asked[N]; vector<int> answer[N] , v; vector< pair<int,int> > v2; int mx = 0 ; vector<int> get(int i){ if(asked[i]) return answer[i]; asked[i] = true; answer[i] = ask(i); if(answer[i][0] + answer[i][1] == mx) v2.push_back(make_pair(answer[i][0],i)); else v.push_back(i); return answer[i]; } int solve(int s,int e){ int res = e; vector<int> v1 = get(s); while(e >= s){ int mid = (s + e) / 2; vector<int> cur = get(mid); if(cur[0] + cur[1] == mx && cur[0] == v1[0]) s = mid + 1; else { res = mid; e = mid - 1; } } return res; } int find_best(int n) { int num = sqrt(n) - 2; int it = 0; if(n <= 5000){ for(int i=0;i<n;i++){ vector<int> cur = get(i); if(cur[0]+cur[1] == 0) return i; } } for(int i=0;i<n && it < 480;i+=num){ vector<int> res = get(i); int cur = res[0] + res[1]; mx = max(mx,cur); it++; } for(int i=1;i<n && it < 480;i+=num){ it++; vector<int> res = get(i); int cur = res[0] + res[1]; mx = max(mx,cur); } int low = 0; while(true){ int high = n - 1; vector<int> cur = get(low); if(cur[0] + cur[1] == 0) return low; if(cur[0] + cur[1] != mx){ low++; continue; } for(int i=0;i<v2.size();i++){ if(v2[i].second >= low && v2[i].first != cur[0]){ high = min(high,v2[i].second); } else if(v2[i].second >= low){ low = max(low,v2[i].second); } } bool flag = false; for(int i=0;i<v.size();i++){ vector<int> tmp = get(v[i]); if(tmp[0] + tmp[1] == 0) return v[i]; if(v[i] > low){ high = min(high,v[i]); } } if(flag) continue; low = solve(low,high); } return 0; }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v2.size();i++){
                ^
prize.cpp:75:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...