제출 #1227454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227454		The_Samurai	The Big Prize (IOI17_prize)	C++20	90 / 100	173 ms	1268 KiB

prize

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

int find_best(int n) {
	int worst = 0;
	auto vec = ask(worst);
	int exp = vec[0] + vec[1];
	if (exp == 0) return 0;
	for (int i = 1; i < min(500, n); i++) {
		auto shit = ask(i);
		if (shit[0] + shit[1] == 0) return i;
		if (shit[0] + shit[1] > exp) {
			exp = shit[0] + shit[1];
			vec = shit;
			worst = i;
		}
	}
	vector<bool> blocked(n);
	
	auto find_next = [&](int worst) -> int {
		int best = -1;
		deque<int> d;
		for (int i = worst; i < n; i++) if (!blocked[i]) d.push_back(i);
		while (!d.empty()) {
			int mid = d.size() / 2;
			auto shit = ask(d[mid]);
			// cout << d.size() << ' ' << d[mid] << ' ' << shit[0] << ' ' << shit[1] << endl;
			if (shit[0] + shit[1] == 0) return d[mid];
			if (vec[0] + vec[1] != shit[0] + shit[1]) {
				blocked[d[mid]] = true;
				d.erase(d.begin() + mid);
				continue;
			}
			if (vec == shit) {
				best = d[mid];
				for (int i = 0; i <= mid; i++) d.pop_front();
			} else {
				while (mid < d.size()) d.pop_back();
			}
		}
		assert(best != -1);
		return best;
	};

	worst = find_next(worst);
	vec = ask(worst);
	if (vec[0] + vec[1] == 0) return worst;

	while (true) {
		for (int i = worst + 1; i < n; i++) {
			auto shit = ask(i);
			if (shit[0] + shit[1] == 0) return i;
			if (shit[0] + shit[1] == vec[0] + vec[1]) {
				vec = shit;
				worst = i;
				break;
			}
		}
		// cout << '\t' << worst << ' ' << vec[0] << ' ' << vec[1] << endl;
		worst = find_next(worst);
		vec = ask(worst);
		if (vec[0] + vec[1] == 0) return worst;
	}
	// assert(false);
	return -1;
}

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