Submission #1340407

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

prize

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

#define pb push_back
#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()>150) 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};

	vector<ll> pi; forn(i,0,100) pi.pb(i);
	forn(k,0,100){
		ll I = rand()%(int)pi.size();
		int i = pi[I];
		ll l = i*2000;
		ll r = min(n-1,i*2000+2000-1);
		pi.erase(pi.begin()+I);
		if(l>r) continue;
		ll re = expand(l,r);
		if(re>-1) return re;
		ll rc = calc(l,r);
		if(rc>-1) return rc;
		
	}
	
	return 0;
}

Compilation message (stderr)

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

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