#include <iostream> #include <vector> #include "prize.h" using namespace std; int tot, Ans = -1, Q, lst = -1; vector<int> res, vec[1<<18]; // vector<int> Ask(int id){ // return {}; // } vector<int> Ask(int id, int &l, int &r){ if (vec[id].size() == 0){ Q++; if (Q > 10000) cout<<1 / 0; vec[id] = ask(id); } if (vec[id][0] + vec[id][1] == 1){ if (vec[id][0] == 1) r = 0; else l = 0; } return vec[id]; } void Solve(int l, int r, int k, int cnt, bool b = 1){ vector<int> rs; if (b == 0 or cnt == 0 or l == r or Ans != -1) return; // cout<<l<<" "<<r<<" "<<cnt<<endl; int mid = (l + r) / 2, L = 1, R = 1; rs = Ask(mid, L, R); // cout<<l<<" "<<mid<<" "<<r<<" "<<k<<" "<<cnt<<" "<<rs[0]<<" "<<rs[1]<<endl; if (rs[0] + rs[1] != tot){ int m1 = mid + 1; if (rs[0] + rs[1] == 0) Ans = mid; while (m1 < r and Ans == -1){ rs = Ask(m1, L, R); if (rs[0] + rs[1] == 0) Ans = m1; if (rs[0] + rs[1] == tot) break; m1++; } // cout<<"here "<<m1<<" "<<rs[0]<<" "<<rs[1]<<endl; if (rand() % 2){ if (m1 == r) Solve(l, mid, k, cnt - (m1 - mid), L); else Solve(l, mid, k, k - rs[1] - (m1 - mid), L); Solve(m1, r, rs[1], cnt - (k - rs[1]), R); } else{ Solve(m1, r, rs[1], cnt - (k - rs[1]), R); if (m1 == r) Solve(l, mid, k, cnt - (m1 - mid), L); else Solve(l, mid, k, k - rs[1] - (m1 - mid), L); } return; } if (rand() % 2){ Solve(l, mid, k, k - rs[1], L); Solve(mid+1, r, rs[1], cnt - (k - rs[1]), R); } else{ Solve(mid+1, r, rs[1], cnt - (k - rs[1]), R); Solve(l, mid, k, k - rs[1], L); } } int find_best(int n){ srand(time(0)); for (int i=0, l=1, r=1;i<min(n, 476);i++){ res = Ask(i, l, r); tot = max(tot, res[0] + res[1]); } Solve(0, n, tot, tot); return Ans; }

prize.cpp: In function 'std::vector<int> Ask(int, int&, int&)':
prize.cpp:17:33: warning: division by zero [-Wdiv-by-zero]
   17 |                         cout<<1 / 0;
      |                               ~~^~~