Submission #1113640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113640		epicci23	The Big Prize (IOI17_prize)	C++17	100 / 100	105 ms	1772 KiB

prize

#include "bits/stdc++.h"
#include "prize.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
 
const int N = 2e5 + 5;
int mx = -1, n;
vector<bool> mark(N, 0);
map<int,vector<int>> dp;
 
vector<int> Ask(int i){
  if(dp.count(i)) return dp[i];
  return dp[i] = ask(i);
}
 
void Learn(int l, int r){
  if(l > r) return;
  if(l == r){
    mark[l] = 1; 
    return;
  }
  int mid = (l+r)/2 , p = -1;
  for(int i=0;i<=(r-l+1)/2;i++){
    if(mid+i<=r){
      vector<int> x = Ask(mid+i);
      if(x[0]+x[1]==mx){
        p=mid+i;
        break;
      }
      mark[mid+i]=1;
    }
    if(mid-i>=l){
      vector<int> x = Ask(mid-i);
      if(x[0]+x[1]==mx){
        p=mid-i;
        break;
      }
      mark[mid-i]=1;
    }
  }
  if(p == -1) return;
  if(l < p && Ask(p)[0] - (l > 0 ? Ask(l-1)[0] : 0) ) Learn(l, p - 1);
  if(p < r && Ask(p)[1] - (r + 1 < n ? Ask(r + 1)[1] : 0) ) Learn(p + 1, r);
}
 
int find_best(int _n){
  n = _n;
  for(int i = 0; i < min(n, 475); i++){
    vector<int> x = Ask(i);
    if(x[0] + x[1] == 0) return i;
    mx = max(mx, x[0] + x[1]);
    if(mx > 30) break;
  }

  Learn(0, n - 1);

  for(int i = 0 ; i < n ; i++){
    if(mark[i]){
      vector<int> x = Ask(i);
      if(x[0] + x[1] == 0) return i;
    }
  }

  return -23;
}

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