Submission #117545

#	Time	Username	Problem	Language	Result	Execution time	Memory
117545		nvmdava	The Big Prize (IOI17_prize)	C++17	0 / 100	28 ms	14624 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> ask(int i);

vector<int> res[200005];
void query(int i){
   if(res[i].empty())
      res[i] = ask(i);
}

bool pos[200005];
set<int> ls[200005];
int ans = -1;

void solve(int l, int r){
   if(ans != -1) return;
   while(l <= r && pos[l++]);
   while(l <= r && pos[r--]);
   if(r < l) return;
   int m = (l + r) >> 1;
   query(m);
   int s = res[m][0] + res[m][1];
   if(s == 0){
      ans = m;
      return;
   }
   pos[m] = 1;

   set<int>::iterator lll = ls[s].insert(m).first;
   set<int>::iterator rrr = lll--;
   set<int>::iterator it = rrr++;
   if(rrr != ls[s].end()){
      int rr = *rrr;
      if(res[m][0] == res[rr][0]){
         for(int i = m + 1; i < rr; i++)
            pos[i] = 1;
      }
   }
   if(it != ls[s].begin()){
      int ll = *lll;
      if(res[ll][0] == res[ll][0])
         for(int i = ll + 1; i < m; i++)
            pos[i] = 1;
   }
   solve(l, m);
   solve(m, r);
}


int find_best(int n) {
   solve(0, n - 1);
   return ans;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80