#include "prize.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> buf; vector<int> qry(int x) { if (buf[x].empty()) { return buf[x] = ask(x); } else { return buf[x]; } } int bcnt; vector<int> tar; void dfs(int l, int r, int cnt, int lp, int rs) { if (l == r) { tar.push_back(l); } else { int rm = l + (r - l) / 2, lm = rm; vector<int> res = qry(lm); while (res[0] + res[1] < bcnt) { tar.push_back(lm); lm--; if (lm < l) { break; } res = qry(lm); } int lc = res[0] - lp; if (lc > 0) { dfs(l, lm - 1, lc, lp, res[1]); } lm = rm; res = qry(lm); while (res[0] + res[1] < bcnt) { tar.push_back(lm); lm++; if (lm > r) { break; } res = qry(lm); } int rc = res[1] - rs; if (rc > 0) { dfs(lm + 1, r, rc, res[0], rs); } } } int find_best(int n) { buf.clear(), buf.resize(n); if (n <= 5000) { for (int i = 0; i < n; i++) { vector<int> res = qry(i); if (res[0] + res[1] == 0) { return i; } } } else { vector<int> rng; for (int i = 0; i < n; i++) { rng.push_back(i); } random_shuffle(rng.begin(), rng.end()); for (int i = 0; i < min(n, 200); i++) { vector<int> res = qry(rng[i]); bcnt = max(bcnt, res[0] + res[1]); } dfs(0, n - 1, bcnt, 0, 0); for (int x : tar) { vector<int> res = qry(x); if (res[0] + res[1] == 0) { return x; } } } }

prize.cpp: In function 'int find_best(int)':
prize.cpp:68:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   68 |         random_shuffle(rng.begin(), rng.end());
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from prize.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~
prize.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
   82 | }
      | ^