Submission #558123

#	Time	Username	Problem	Language	Result	Execution time	Memory
558123		aryan12	The Big Prize (IOI17_prize)	C++17	100 / 100	63 ms	11268 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500;

int find_best(int n)
{
	vector<vector<int> > store(n + 1, vector<int> (2));
	for(int i = 0; i <= n; i++)
	{
		store[i][0] = -1;
		store[i][1] = -1;
	}
	int previous_optimal = -1;
	store[0] = ask(0);
	if(store[0][0] == 0 && store[0][1] == 0)
	{
		return 0;
	}
	int max_sum = store[0][0] + store[0][1];
	for(int atleastbefore = 1; atleastbefore <= n; atleastbefore++)
	{
		int l = 0, r = n - 1;
		int current_optimal = 0;
		while(l < r)
		{
			int mid = (l + r) / 2;
			// cout << "l = " << l << ", r = " << r << ", previous_optimal = " << previous_optimal << "\n";
			if(mid <= previous_optimal)
			{
				l = mid + 1;
				current_optimal = mid + 1;
				continue;
			}
			if(store[mid][0] == -1)
			{
				store[mid] = ask(mid);
			}
			if(store[mid][0] + store[mid][1] == 0)
			{
				return mid;
			}
			if(store[mid][0] + store[mid][1] > max_sum)
			{
				max_sum = store[mid][0] + store[mid][1];
				l = 0, r = n - 1;
				current_optimal = 0;
				continue;
			}
			if(store[mid][0] < atleastbefore && store[mid][0] + store[mid][1] == max_sum)
			{
				l = mid + 1;
				current_optimal = mid + 1;
			}
			else
			{
				r = mid;
			}
		}
		assert(current_optimal >= 0 && current_optimal < n);
		previous_optimal = current_optimal;
		if(store[previous_optimal][0] == -1)
		{
			store[previous_optimal] = ask(previous_optimal);
		}
		if(store[previous_optimal][0] + store[previous_optimal][1] == 0)
		{
			return previous_optimal;
		}
	}
	return -1;
}

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