제출 #876313

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

prize

#include "prize.h"
#include <iostream>
#define ll long long
 
using namespace std;
 
ll f = -1;
vector <int> R;
void solve(ll l, ll r, ll ql, ll qr) {
	if (l > r || ql + qr == R[0] + R[1]) return;
	ll mid = (l+r)/2;
	for (int i=mid; i<=r; ++i) {
		auto u = ask(i);
		if (!u[0] && !u[1]) {
			f = i;
			return;
		}
		else if (u[0]+u[1] == R[0]+R[1]) {
			solve(l, mid-1, ql, u[1]+(i-mid));
			if (f != -1) return;
			solve(i+1, r, u[0], qr);
			return;
		}
	}
	solve(l, mid-1, ql, qr+(r-mid+1));
}
 
void get(ll l, ll r) {
	if (l == r) {
		R = ask(l);
		return;
	}
	ll mid = (l+r+1)/2;
	auto u = ask(mid);
	if (u[0] != mid) get(l, mid-1);
	else get(mid, r);
}
 
int find_best(int n) {
  	get(0, n-1);
	solve(0, n-1, 0, 0);
	return f;
}

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