Submission #390953

#	Time	Username	Problem	Language	Result	Execution time	Memory
390953		alishahali1382	The Big Prize (IOI17_prize)	C++14	97.60 / 100	67 ms	1864 KiB

prize

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

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

const int inf=1000000100;
const int MAXN=200010;

int n, m, k, shit, ans=-1;
pii A[MAXN];

pii Ask(int i){
	if (A[i].first!=-1) return A[i];
	auto v=ask(i);
	A[i]={v[0], v[1]};
	return A[i];
}
int ord(int i){
	return Ask(i).first+Ask(i).second;
}
void divide(int tl, int tr, int ted){
	if (!ted || tr-tl<1 || ans!=-1) return ;
	int mid=(tl+tr)>>1;
	if (tr-tl>10000) mid-=200;
	for (int i=mid; i<tr && ted; i++){
		if (!ord(i)){
			ans=i;
			return ;
		}
		if (ord(i)!=shit){
			ted--;
			continue ;
		}
		int tedl=Ask(i).first-Ask(tl-1).first-(i-mid);
		divide(tl, mid, tedl);
		divide(i+1, tr, ted-tedl);
		return ;
	}
	divide(tl, mid, ted);
}

int find_best(int _n){
	memset(A, -1, sizeof(A));
	n=_n;/*
	if (n<5000){
		for (int i=0; i<n; i++)
			if (!ord(i)) return i;
		assert(0);
	}*/
	int T=480;
	for (int i=0; i<T; i++){
		if (!ord(i)) return i;
		shit=max(shit, ord(i));
	}
	for (int i=T; i<n; i++){
		if (!ord(i)) return i;
		if (ord(i)==shit){
			divide(i+1, n, Ask(i).second);
			return ans;
		}
	}
	assert(0);
}

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