Submission #1060906

#TimeUsernameProblemLanguageResultExecution timeMemory
1060906onbertThe Big Prize (IOI17_prize)C++17
90 / 100
63 ms11604 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; const int maxn = 2e5; vector<int> vals[maxn]; vector<int> qry(int i) { if (vals[i][0]!=-1) return vals[i]; else return vals[i] = ask(i); } int find_best(int n) { for (int i=0;i<n;i++) vals[i] = {-1, -1}; int mx = 0; for (int i=0;i<n;i++) { vector<int> x = qry(i); mx = max(x[0]+x[1], mx); if (x[0] + x[1] == 0) return i; int l = i, r = n-1; while (l<r && x[0]+x[1] == mx) { int mid = (l+r+1)/2; vector<int> y = qry(mid); mx = max(y[0]+y[1], mx); if (y[0]+y[1]==0) return mid; if (y[0]!=x[0] || y[1]!=x[1]) r = mid-1; else l = mid; } i = l; } }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...