Submission #70159

#	Time	Username	Problem	Language	Result	Execution time	Memory
70159		E869120	커다란 상품 (IOI17_prize)	C++14	20 / 100	122 ms	684 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: 20 / 20
• Subtask 2: 0 / 80