Submission #287268

#	Time	Username	Problem	Language	Result	Execution time	Memory
287268		mosiashvililuka	The Big Prize (IOI17_prize)	C++14	20 / 100	3053 ms	2048 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,sq,lef,rig,mid,pas,mx,lf[200009],rg[200009],cnt;
int find_best(int n) {
	vector <int> ans,lp;
	lp.resize(2);
	a=n;
	for(i=0; i<a+2; i++){
		lf[i]=-1;rg[i]=-1;
	}
	int sq=sqrt(a);
	for(i=1; i<=sq+1; i++){
		ans=ask(i-1);
		cnt++;
		if(cnt>=9999){
			for(int h=0; ; h++) ;
		}
		if(ans[0]+ans[1]==0){
			return i-1;
		}
		lf[i]=ans[0];
		rg[i]=ans[1];
		mx=max(ans[0]+ans[1],mx);
	}
	for(i=sq+1; ; i--){
		if(lf[i]+rg[i]==mx) break;
	}
	while(1){
		lef=i;rig=a+1;
		lp[0]=lf[i];lp[1]=rg[i];
		pas=0;
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			if(lf[mid]==-1){
				ans=ask(mid-1);
				cnt++;
		if(cnt>=9999){
			for(int h=0; ; h++) ;
		}
			}else{
				ans[0]=lf[mid];ans[1]=rg[mid];
			}
			//ans=ask(mid-1);
			lf[mid]=ans[0];rg[mid]=ans[1];
			if(ans[0]==0&&ans[1]==0){
				return mid-1;
			}
			if(ans[0]==lp[0]&&ans[1]==lp[1]){
				lef=mid;
			}else{
				rig=mid;
				pas=mid;
			}
		}
		i=pas;
		for(i=i+1; ; i++){
			if(lf[i]==-1){
				ans=ask(i-1);
				cnt++;
		if(cnt>=9999){
			for(int h=0; ; h++) ;
		}
			}else{
				ans[0]=lf[i];ans[1]=rg[i];
			}
			//ans=ask(i-1);
			lf[i]=ans[0];rg[i]=ans[1];
			if(ans[0]+ans[1]==0){
				return i-1;
			}
			if(ans[0]+ans[1]==mx){
				break;
			}
		}
	}
}

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