Submission #423112

#	Time	Username	Problem	Language	Result	Execution time	Memory
423112		albertolg101	The Big Prize (IOI17_prize)	C++17	0 / 100	112 ms	288 KiB

prize

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

using namespace std; 

int find_best(int n) {

	int sum = 0, pos = -1;
	vector<int> ar;
	
	while(2 * sum * sum <= n)
	{
		pos++;

		ar = ask(pos);
		sum = ar[0] + ar[1];

		if(ar[1] == 0)
			return 0;
	}

	vector<vector<int>> query(n);

	while(true)
	{
		for(int i = 17 ; i >= 0 ; i--)
		{
			int target = pos + (1<<i);

			if(target < n)
			{
				if(query[target].empty()) 
					query[target] = ask(target);

				if(query[target][0] + query[target][1] == sum and query[target][1] == ar[1])
					pos = target;
			}
		}

		pos++;
		
		while(true)
		{
			if(query[pos].empty())
				query[pos] = ask(pos);

			ar = query[pos];

			if(ar[0] + ar[1] == 0)
				return pos;

			else if(ar[0] + ar[1] == sum)
				break;
		
			pos++;
		}
	} 
}

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