제출 #70105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70105		E869120	커다란 상품 (IOI17_prize)	C++14	0 / 100	8 ms	2604 KiB

prize

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

vector<int>vec;

int find_best(int n) {
	// -------------- 前処理 -----------------
	for(int i=0;i<n;i++) vec.push_back(i);
	
	while(vec.size() >= 2){
		int maxn=0;
		for(int i=0;i<30;i++){
			vector<int>P = ask(vec[rand()%vec.size()]);
			maxn = max(maxn, P[0] + P[1]);
		}
		assert(maxn>(int)vec.size());
		vector<int>vec2; int ret = -1;
		for(int h=0;h<maxn;h++){
			int cx = 0;
			for(int i=17;i>=0;i--){
				int pos = cx + (1 << i) - 1; if(pos >= (int)vec.size()) pos = vec.size() - 1;
				vector<int>L = ask(vec[pos]);
				if((L[0] + L[1] == maxn && L[0] == h) || pos <= ret) cx += (1 << i);
			}
			vec2.push_back(vec[cx]); ret = cx;
		}
		vec = vec2;
	}
	return vec[0];
}

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