Submission #1340397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340397		JuanJL	The Big Prize (IOI17_prize)	C++20	97.25 / 100	30 ms	20476 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

#define forn(i,a,b) for(int i = a; i<b; i++)

using namespace std;
typedef long long ll;

map<int,vector<int>> ret;
map<int,bool> isq;
map<int,int> rnd[200000+5];
map<int,bool> isrnd[200000+5];
ll cnt = 0;
vector<int> aask(int i ){
	if(isq[i]) return ret[i];
	isq[i]=true;
	ret[i]=ask(i);
	cnt++;
/*	while(cnt>9990){
		exit(0);
	}*/
	
	//cout<<cnt<<'\n';
	return ret[i];
}

ll calc(ll l , ll r){
	if(l==r-1){
		//	cout<<aask(l)[0]<<" <-> "<<aask(l)[1]<<'\n';
			if(aask(l)[0]==aask(l)[1]&&aask(l)[0]==0) return l;
			if(aask(r)[0]==aask(r)[1]&&aask(r)[0]==0) return r;
			return -1;
		}
	if(aask(l)[0]==aask(r)[0] && aask(l)[1]==aask(r)[1]) return -1;
	
	ll mid = (l+r)/2;
	ll ncase = rnd[l][r];
	if(!isrnd[l][r]) ncase=rand()%2;

	if(ncase==0){
		ll prl = calc(l,mid);
		if(prl>-1) return prl;
	
		ll prr = calc(mid,r);
		if(prr>-1) return prr;
	}else{
		ll prr = calc(mid,r);
		if(prr>-1) return prr;

		ll prl = calc(l,mid);
		if(prl>-1) return prl;
	}	
	
}

ll expand(ll l, ll r){
	ll mid =(l+r)/2;
	if((int)ret.size()>300) return -1;
	if(l==r-1){
		if(aask(l)[0]==aask(l)[1]&&aask(l)[0]==0) return l;
					if(aask(r)[0]==aask(r)[1]&&aask(r)[0]==0) return r;
					return -1;
		
	}
	if(aask(l)[0]==aask(r)[0] && aask(l)[1]==aask(r)[1]) return- 1;
	rnd[l][r]=rand()%2;
	isrnd[l][r]=true;
	ll ncase = rnd[l][r];
	if(ncase==0){
		ll prl = expand(l,mid);
		if(prl>-1) return prl;
		
		ll prr = expand(mid,r);
		if(prr>-1) return prr;
	}else{
		ll prr = expand(mid,r);
		if(prr>-1) return prr;
	
		ll prl = expand(l,mid);
		if(prl>-1) return prl;
	}	
}

int find_best(int n) {
	srand(time(NULL));
	ll i = 0;
	vector<int> ares = {-1,-1};
	vector<int> last = {-1,-1};

	ll re = expand(0,n-1);
	if(re>-1) return re;
	return calc(0,n-1);
	
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'll calc(ll, ll)':
prize.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^
prize.cpp: In function 'll expand(ll, ll)':
prize.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
   82 | }
      | ^

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