제출 #964731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964731		AdamGS	커다란 상품 (IOI17_prize)	C++17	100 / 100	32 ms	7388 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
vector<int>P[LIM];
int odw[LIM], ma, n;
void pytaj(int x) {
  if(odw[x]) return;
  odw[x]=1;
  P[x]=ask(x);
  ma=max(ma, P[x][0]+P[x][1]);
}
bool dobry(int x) {
  if(x<0 || x>=n) return false;
  pytaj(x);
  return P[x][0]+P[x][1]<ma;
}
bool wygrany(int x) {
  if(x<0 || x>=n) return false;
  pytaj(x);
  return P[x][0]+P[x][1]==0;
}
int solve(int l, int r) {
  if(l>r) return -1;
  if(wygrany(l-1)) return l-1;
  if(dobry(l-1)) return solve(l+1, r);
  if(wygrany(r+1)) return r+1;
  if(dobry(r+1)) return solve(l, r-1);
  int a=ma;
  if(l) a=P[l-1][1];
  if(r<n-1) a-=P[r+1][1];
  if(!a) return -1;
  int mid=(l+r)/2;
  if(wygrany(mid)) return mid;
  int p=solve(l, mid-1);
  if(p!=-1) return p;
  return solve(mid+1, r);
}
int find_best(int N) {
  n=N;
  if(n<=5000) {
    rep(i, n) {
      pytaj(i);
      if(P[i][0]+P[i][1]==0) return i;
    }
  }
  int x=n/500;
  rep(i, 499) if(wygrany(x*(i+1))) return x*(i+1);
  int p=solve(0, x-1);
  if(p!=-1) return p;
  rep(i, 498) {
    p=solve(x*(i+1)+1, x*(i+2)-1);
    if(p!=-1) return p;
  }
  return solve(x*499+1, n-1);
}

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