Submission #1340385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340385		JuanJL	The Big Prize (IOI17_prize)	C++20	97.60 / 100	19 ms	1184 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;
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 = 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;
	}	
	
}

void expand(ll l, ll r){
	ll mid =(l+r)/2;
	if((int)ret.size()>300) return;
	if(l==r-1) return;
	if(aask(l)[0]==aask(r)[0] && aask(l)[1]==aask(r)[1]) return;
	expand(l,mid);
	expand(mid,r);
}

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

	expand(0,n-1);
	return calc(0,n-1);
	
	return 0;
}

Compilation message (stderr)

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

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