제출 #1157406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157406		vjudge3	커다란 상품 (IOI17_prize)	C++20	92.71 / 100	14 ms	408 KiB

prize

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

vector<int> ask(int i);

int candidate_cnt;

int query(int l, int r, int cnt, int lcnt, int rcnt) {
	if (l > r || !cnt) return -1;
	int mid = (l+r)/2;
	vector<int> res = ask(mid);
	if (res[0]+res[1] == 0) return mid;
	if (res[0]+res[1] == candidate_cnt) return max(query(l, mid, cnt - (res[1]-rcnt), lcnt, res[1]), query(mid+1, r, cnt - (res[0]-lcnt), res[0], rcnt));
	int midl = mid-1, midr = mid+1;
	vector<int> lres = {0, 0}, rres = {0, 0};
	for (; midl >= l; midl--) {
		lres = ask(midl);
		if (lres[0]+lres[1] == 0) return midl;
		if (lres[0]+lres[1] == candidate_cnt) break;
	}
	for (; midr <= r; midr++) {
		rres = ask(midr);
		if (rres[0]+rres[1] == 0) return midr;
		if (rres[0]+rres[1] == candidate_cnt) break;
	}
	return max(query(l, midl, cnt - (lres[1]-rcnt), lcnt, lres[1]), query(midr, r, cnt - (rres[0]-lcnt), rres[0], rcnt));
}

int find_best(int n) {
	for (int i = 0; i < min(500, n); i++) {
		vector<int> res = ask(i);
		candidate_cnt = max(candidate_cnt, res[0]+res[1]);
	}
	return query(0, n-1, candidate_cnt, 0, 0);
}

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