Submission #39397

#TimeUsernameProblemLanguageResultExecution timeMemory
39397mohammad_kilaniThe Big Prize (IOI17_prize)C++14
95.13 / 100
49 ms7224 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) { srand(time(0)); int num = min(n,480); for(int i=0;i<num;i++){ 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++){ if(v[i] > low){ vector<int> tmp = get(v[i]-1); if(tmp[0] == cur[0]){ low = v[i]; flag = true; break; } 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:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v2.size();i++){
                ^
prize.cpp:62: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...