Submission #412635

#	Time	Username	Problem	Language	Result	Execution time	Memory
412635		nxteru	The Big Prize (IOI17_prize)	C++14	100 / 100	66 ms	1864 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int ma,mma;
pair<int,int> ret[200005];
int lt(int i){
	if(ret[i].first==-1){
		vector<int>x=ask(i);
		ret[i]=make_pair(x[0],x[1]);
	}
	return ret[i].first;
}
int rt(int i){
	if(ret[i].second==-1){
		vector<int>x=ask(i);
		ret[i]=make_pair(x[0],x[1]);
	}
	return ret[i].second;
}
int ss(int i){
	return lt(i)+rt(i);
}
int type(int i){
	int x=ss(i);
	if(x==0)return i;
	else if(ma<x){
		mma=x;
		return -1;
	}else if(ma==x)return -2;
	else return -3;
}
void left(int l,int &i){
	while(l<=i&&type(i)==-3)i--;
}
void right(int r,int &i){
	while(i<=r&&type(i)==-3)i++;
}
int solve(int l,int r,int s,int t){
	if(r<l)return -3;
	if(l==r)return type(l);
	int ml=(l+r)/2,mr=ml;
	left(l,ml);
	int res=-3;
	if(l<=ml&&type(ml)>=-1)return type(ml);
	if(l<ml&&s-rt(ml)>0)res=solve(l,ml-1,s,rt(ml));
	if(res>=-1)return res;
	right(r,mr);
	if(mr<=r&&type(mr)>=-1)return type(mr);
	if(mr<r&&rt(mr)-t>0)res=solve(mr+1,r,rt(mr),t);
	return res;
}
int find_best(int n){
	for(int i=0;i<n;i++)ret[i]=make_pair(-1,-1);
	for(int i=0;i<100;i++){
		if(type(i)>=0)return type(i);
		ma=mma;
	}
	while(1){
		ma=mma;
		int la=100;
		right(n-1,la);
		if(type(la)>=0)return type(la);
		if(type(la)==-1)continue;
		while(1){
			int pl=min(la+256,n-1),pr=pl;
			left(la,pl);
			if(type(pl)>=0)return type(pl);
			if(type(pl)==-1)break;
			int res=solve(la+1,pl-1,rt(la),rt(pl));
			if(res>=0)return res;
			if(res==-1)break;
			right(n-1,pr);
			if(type(pr)>=0)return type(pr);
			if(type(pr)==-1)return -1;
			la=pr;
		}
	}
}

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