제출 #574543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
574543		valerikk	커다란 상품 (IOI17_prize)	C++17	90 / 100	95 ms	336 KiB

prize

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

using namespace std;

namespace {

int mx_cnt;

}

int solve(int l, int r, vector<int> h, int f) {
	if (l > r) 
		return -1;

	if (l == r) {
		auto a = f == -1 ? ask(l) : h;
		if (a[0] + a[1] == 0)
			return l;
		return -1;
	}

	auto al = f == 0 ? h : ask(l);
	auto ar = f == 1 ? h : ask(r);

	if (al[0] + al[1] == 0)
		return l;
	if (ar[0] + ar[1] == 0)
		return r;

	if (al[0] + al[1] == mx_cnt && ar[0] + ar[1] == mx_cnt && al[0] == ar[0]) 
		return -1;

	int m = (l + r) / 2;

	return max(solve(l, m, al, 0), solve(m + 1, r, ar, 1));
}	

int find_best(int n) {
	mx_cnt = 0;

	for (int i = 0; i < min(n, 500); ++i) {
		auto a = ask(i);

		if (a[0] + a[1] == 0)
			return i;

		mx_cnt = max(mx_cnt, a[0] + a[1]);
	}

	return solve(0, n - 1, {}, -1);
}

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