Submission #1200463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200463		mertbbm	The Big Prize (IOI17_prize)	C++20	95.65 / 100	14 ms	1000 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<ld,ld>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
int ran(int index){return rng()%index;}

//ask()

int blk=290;
int sz=480;
map<int,vector<int>>mp;

vector<int>f(int index){
	if(mp.find(index)!=mp.end()) return mp[index];
	return mp[index]=ask(index);
}

int32_t find_best(int32_t n){
	pii maxi={-1,-1};
	for(int x=0;x<min(n,sz);x++){
		vector<int>hold=f(x);
		maxi=max(maxi,{hold[0]+hold[1],x});
		if(hold[0]+hold[1]==0) return x;
	}
	vector<int>nxt=f(sz);
	int cur=sz;
	while(cur<n){
		vector<int>take=nxt;
		if(cur+blk<n) nxt=f(cur+blk);
		else nxt={(int)1e9,(int)1e9};
		if(take==nxt&&take[0]+take[1]==maxi.first){
			cur+=blk;
			continue;
		}
		int target=min(cur+blk,n);
		int counter2=0;
		while(cur<target){
			counter2++;
			vector<int>check;
			if(cur==target-blk) check=take;
			else check=f(cur);
			if(check[0]+check[1]==0) return cur;
			if(check[0]+check[1]!=maxi.first){
				cur++;
				continue;
			}
			if(check==nxt){
				cur=target;
				continue;
			}
			int l=cur+1;
			int r=target-1;
			int best=r;
			int mid;
			int counter=0;
			while(l<=r){
				counter++;
				mid=(l+r)/2;
				vector<int>hold=f(mid);
				if(hold==check){
					l=mid+1;
				}
				else{
					best=mid;
					if(hold[0]+hold[1]==0) return mid;
					r=mid-1;
				}
			}
			assert(counter<=9);
			cur=min(best+2,target);
		}
	}
	return -1;
}

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