제출 #1184066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184066		alterio	The Big Prize (IOI17_prize)	C++20	20 / 100	27 ms	6304 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxn = 2e5 + 10;

int L, R;

vector<int> know[mxn];

vector<int> get(int x) {
	if (know[x].size()) return know[x];
	return know[x] = ask(x);
}

void solve(int l, int r) {
	if (l > R || r < L || l > r) return;
	if (get(l)[0] + get(l)[1] == 0) {
		L = R = l;
		return;
	}
	if (get(r)[0] + get(r)[1] == 0) {
		L = R = r;
		return;
	}
	if (r - l <= 1) return;
	vector<int> valL = get(l), valR = get(r);
	int x = uniform_int_distribution<int> (l + 1, r - 1)(rng);
	vector<int> valX = get(x);
	int sumL = valL[0] + valL[1], sumR = valR[0] + valR[1], sumX = valX[0] + valX[1];
	if (sumX == 0) {
		L = R = x;
		return;
	}
	if (valX[0] + valX[1] == 1) {
		if (valX[0] == 0) {
			L = max(L, x + 1);
			solve(x + 1, r - 1);
		}
		else {
			R = min(R, x - 1);
			solve(l + 1, x - 1);
		}
	}
	else {
		if (sumX < sumL && sumX < sumR) {
			if (valX[0] > valX[1]) solve(l, x - 1);
			else solve(x + 1, r);
		}
		else solve(l + 1, r - 1);
	}
}

int find_best(int n) {
	L = 0, R = n - 1;
	solve(L, R);
	return L;
}

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