#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define all(x) x.begin(),x.end()
typedef vector<int> vi;
map<int , vi> mp;
inline vi F(int i) {
if (mp.count(i)) return mp[i];
if (mp.size() + 1 > 10000) assert(0);
return (mp[i] = ask(i));
}
inline int sum(vi me) {
return accumulate(all(me) , 0);
}
int least, ans, ltof , rtof;
bitset<400000> mark;
void solve(int l , int r, int le , int ri) {
if (l >= rtod || r <= ltof) return;
if (ans != -1) return;
if (l >= r) return;
if (le + ri == least) return;
int mid = l + r >> 1;
bool happy = false;
rep(i , 0 , r - l) {
if (i & 1) mid -= i;
else mid += i;
vi me = F(mid);
if (me[0] == 0) ltof = max(ltof , mid - 1);
if (me[1] == 0) rotf = min(rtof , mid + 1);
mark[mid] = true;
if (sum(me) == 0) ans = mid;
if (sum(me) == least) {
happy = true;
break;
}
}
if (!happy) return;
int ptr = l;
while (!mark[ptr]) ptr++;
int ptr2 = ptr;
while (sum(F(ptr2)) != least) ptr2++;
int ptr3 = r - 1;
while (!mark[ptr3]) ptr3--;
int ptr4 = ptr3;
while (sum(F(ptr4)) != least) ptr4--;
solve(l , ptr , le , ptr2 - ptr + F(ptr2)[1]);
solve(ptr3 + 1 , r , ptr3 - ptr4 + F(ptr4)[0], ri);
}
int find_best(int n) {
mp.clear();
rep(i , 0 , n) mark[i] = false;
ltop = 0;
rtof= n;
least = -1; ans = -1;
for (int i = 1; (i - 2) * (i - 2) <= n; i++) {
least = max(least , sum(F(i - 1)));
if (sum(F(i - 1)) == 0) return i - 1;
}
solve(0 , n , 0 , 0);
return ans;
}
Compilation message
prize.cpp: In function 'void solve(int, int, int, int)':
prize.cpp:27:11: error: 'rtod' was not declared in this scope
if (l >= rtod || r <= ltof) return;
^~~~
prize.cpp:27:11: note: suggested alternative: 'rtof'
if (l >= rtod || r <= ltof) return;
^~~~
rtof
prize.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
prize.cpp:38:19: error: 'rotf' was not declared in this scope
if (me[1] == 0) rotf = min(rtof , mid + 1);
^~~~
prize.cpp:38:19: note: suggested alternative: 'rtof'
if (me[1] == 0) rotf = min(rtof , mid + 1);
^~~~
rtof
prize.cpp: In function 'int find_best(int)':
prize.cpp:72:2: error: 'ltop' was not declared in this scope
ltop = 0;
^~~~
prize.cpp:72:2: note: suggested alternative: 'ltof'
ltop = 0;
^~~~
ltof
