Submission #73255

#	Time	Username	Problem	Language	Result	Execution time	Memory
73255		Navick	The Big Prize (IOI17_prize)	C++17	97.61 / 100	61 ms	576 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) {
	
	int umax = 0;

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

	solve(maxN, n, ted - umax, umax, 0);

	return p;
}

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