Submission #1200405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200405		mertbbm	The Big Prize (IOI17_prize)	C++20	20 / 100	24 ms	412 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=270;
int sz=450;

int32_t find_best(int32_t n){
	pii maxi={-1,-1};
	for(int x=0;x<min(n,sz);x++){
		vector<int>hold=ask(x);
		maxi=max(maxi,{hold[0]+hold[1],x});
		if(hold[0]+hold[1]==0) return x;
	}
	vector<int>nxt=ask(sz);
	int cur=sz;
	while(cur<n){
		vector<int>take=nxt;
		if(cur+blk<n) nxt=ask(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);
		while(cur<target){
			vector<int>check;
			if(cur==target-blk) check=take;
			else check=ask(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;
			int r=target-1;
			int best=l-1;
			int mid;
			while(l<=r){
				mid=(l+r)/2;
				vector<int>hold=ask(mid);
				if(hold==check){
					best=mid;
					l=mid+1;
				}
				else r=mid-1;
			}
			cur=min(best+1,target);
		}
	}
	return -1;
}

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