Submission #70136

#	Time	Username	Problem	Language	Result	Execution time	Memory
70136		E869120	The Big Prize (IOI17_prize)	C++14	20 / 100	83 ms	588 KiB

prize

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

int Rand(){
	int G=0;
	for(int i=0;i<30;i++){G+=(1<<i)*(rand()%2);}
	return G;
}

int find_best(int n) {
	int maxn=0;
	for(int i=0;i<100;i++){
		vector<int>p=ask(rand()%n);
		maxn=max(maxn,p[0]+p[1]);
	}
	int cx=0;
	for(int i=0;i<maxn;i++){
		int L=cx,R=n+1,M,res=cx-1;
		for(int j=0;j<21;j++){
			M=(L+R)/2;int MM=min(M,n-1);
			vector<int>p=ask(MM);
			if(p[0]+p[1]==maxn && p[0]==i){res=max(res,MM);L=MM;}
			else{R=MM;}
		}
		vector<int>p=ask(res+1);
		if(p[0]==0 && p[1]==0) return res+1;
		cx=res+2;
	}
	return -1;
}

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