Submission #73248

#	Time	Username	Problem	Language	Result	Execution time	Memory
73248		Navick	The Big Prize (IOI17_prize)	C++17	97.61 / 100	71 ms	628 KiB

prize

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

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;

const int maxN = 480;

int p = -1, ted;

void solve(int l, int r, int k, int kl, int kr)
{
	if(r - l <= 0) return ;
	if(k == 0) return ;
	if(p != -1) return ;

	if(r - l < 2)
	{
		if(l < maxN) return ;
		vector <int> t = ask(l);
		if(t[0] + t[1] == 0) p = l;
		return ;
	}

	int mid = (l + r)/2;

	int i = mid, cnt = 0;
	bool ok = false;

	while(i < r)
	{
		vector <int> t = ask(i);
		if(t[0] + t[1] < ted){
			if(t[0] + t[1] == 0) p = i;
			i ++;
			cnt ++;
		}else
		{
			int a = t[0], b = t[1];
			a -= kl; a -= cnt;
			solve(l, mid, a, kl, cnt + t[1]);
			solve(i + 1, r, b - kr, t[0], kr);
			ok = true;
			break ;
		}
	}
	
	if(ok) return ;
	
	solve(l, mid, k - cnt, kl, cnt + kr);

	return ;

}

int find_best(int n) {

	for(int i = 0; i < min(maxN, n); i++) {
		vector<int> res = ask(i);
		if(res[0] + res[1] == 0)
			return i;
		ted = max(ted, res[0] + res[1]);
	}

	solve(0, n, ted, 0, 0);

	return p;
}

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