제출 #70157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70157		E869120	The Big Prize (IOI17_prize)	C++14	0 / 100	5 ms	676 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<87;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 < 20; j++) {
			M = (L + R) / 2; int MM = min(M,n-1);
			vector<int>p=ask(MM); assert(p[0] + p[1] > maxn);
			if(p[0]+p[1] == maxn && p[0] == i) { res = max(res, MM); L = MM; }
			else { R = MM; }
		}
		vector<int>p = ask(res+1); assert(p[0] + p[1] > maxn);
		if(p[0]==0 && p[1]==0) return res+1;
		cx=res+2;
	}
	return -1;
}

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