oj.uz

Submission #117546

# Submission time Handle Problem Language Result Execution time Memory
117546 2019-06-16T14:14:32 Z nvmdava The Big Prize (IOI17_prize) C++17
0 / 100
 14 ms 14592 KB 
#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]) l++;
   while(l <= r && pos[r]) 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;
   }
   if(res[m][0] != 0)
      solve(l, m);
   if(res[m][1] != 0)
      solve(m, r);
}


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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 14592 KB Integer -1 violates the range [0, 199999]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14464 KB Integer -1 violates the range [0, 199999]
2 Halted 0 ms 0 KB -