제출 #1113345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113345		epicci23	커다란 상품 (IOI17_prize)	C++17	20 / 100	195 ms	1536 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 S = 100;
const int S2 = 20;

int suf = -1;
vector<int> Cache={-1,-1};
map<int,vector<int>> dp;

vector<int> Ask(int i){
  if(dp.count(i)) return dp[i];
  return dp[i]=ask(i);
}

int ask_all(int l,int r){
  for(int i=l;i<=r;i++){
    vector<int> x = Ask(i);
    if(x[0]+x[1]==0) return i;
    if(x[1]==suf) Cache=x;
    else suf--;
  }
  return -23;
}

int Learn(int l,int r){
  if(l>r) return -1;
  if(l==r){
    auto u = Ask(l);
    if(u[0]+u[1]==0) return l;
    if(u[1]==suf) Cache=u;
    else suf--;
    return -1;
  }
  int BL = (int)sqrtl(r-l+1);
  auto u = Ask(l+BL);
  if(u[0]+u[1]==0) return l+BL;
  if(u[1]==suf) return Learn(l+BL+1,r);
  int lf = Learn(l,l+BL-1);
  if(lf!=-1) return lf;
  if(u[0]+u[1]!=Cache[0]+Cache[1]) suf--;
  return Learn(l+BL+1,r);
}

int find_best(int n){
  if(n<=1000) return ask_all(0,n-1);
  for(int i=0;i<=500;i++){
    vector<int> x = Ask(i);
    if(x[0]+x[1]==0) return i;
    if(x[0]+x[1]>=Cache[0]+Cache[1]){
      Cache=x;
      suf=Cache[1];
    }
    else suf--;
  }
  return Learn(501,n-1);
}

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