Submission #289103

#	Time	Username	Problem	Language	Result	Execution time	Memory
289103		wdjpng	The Big Prize (IOI17_prize)	C++17	92.77 / 100	67 ms	384 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define lint long long
#define rep(i, n) for (int i = 0; i < n; i++)

using namespace std;

int res = -1;
struct state{
	int i; int toLeft; int toRight;
	int sum(){
		return toLeft+toRight;
	}
};
void get(state l, state r){
	if(r.i-l.i<2){return;}
	if(r.toRight==l.toRight){return;}
	if(res>=0){return;}

	if(r.toRight-l.toRight==r.i-l.i-1)
	{
		for(int i = l.i+1; i < r.i; i++){
			vector<int>ans=ask(i);
			if(ans[0]+ans[1]==0) res = i;
		}
	} else
	{
		int mid = (l.i+r.i)/2;
		vector<int>tmp=ask(mid);
		state ansl = state({mid, tmp[0], tmp[1]});
		state ansr = ansl;

		while(ansl.sum()<l.sum()){
			if(ansl.sum()==0){res=ansl.i; return;}
			
			tmp=ask(ansl.i-1);
			ansl = state({ansl.i-1, tmp[0], tmp[1]});
		}

		while(ansr.sum()<l.sum()){
			if(ansr.sum()==0){res=ansr.i; return;}
			
			tmp=ask(ansr.i+1);
			ansr = state({ansr.i+1, tmp[0], tmp[1]});
		}

		get(l, ansl);
		get(ansr, r);
	}
}

state getState(int i){
	vector<int>tmp=ask(i);
	return state({i, tmp[0], tmp[1]});
}
int find_best(int n)
{
	if(n<5000&&false){
		rep(i, n){
			vector<int>ans=ask(i);
			if(ans[0]+ans[1]==0){return i;}
		}
	}

	state l = getState(0);
	state r = getState(n-1);
	
	int maxx=0;
	rep(i, 20){
		state s = getState(rand()%n);
		maxx=max(maxx, s.sum());
	}
	while(l.sum()<maxx){
		if(l.sum()==0){return l.i;}
		l=getState(l.i+1);
	}

	while(r.sum()<maxx){
		if(r.sum()==0){return r.i;}
		r=getState(r.i-1);
	}

	get(l,r);
	return res;
}

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