#include "prize.h" #include <vector> using namespace std; int nonlollipop = 0; int diamond_search(int a, int b, int L, int R) //extra non-lollipops on left and right { if(b < a) return -1; else if(nonlollipop - L - R == (b-a+1)) //a..b is completely filled with prizes { for(int i = a; i <= b; i++) { vector<int> A = ask(i); if(A[0] + A[1] == 0) return i; } return -1; } vector<int> A; int m; for(m = (a+b)/2; m <= b; m++) { A = ask(m); if(A[0] + A[1] == 0) return m; else if(A[0] + A[1] == nonlollipop) //m is a lollipop { return max( diamond_search(a, (a+b)/2-1, L, A[1]), diamond_search(m+1, b, A[0], R) ); } } return diamond_search(a, (a+b)/2-1, L, R + (b - (a+b)/2 + 1)); } int find_best(int n) { for(int i = 1; i <= min(500, n); i++) { vector<int> A = ask(i); nonlollipop = max(nonlollipop, A[0]+A[1]); } return diamond_search(0, n-1, 0, 0); }