Submission #38410

#	Time	Username	Problem	Language	Result	Execution time	Memory
38410		MatheusLealV	The Big Prize (IOI17_prize)	C++14	20 / 100	43 ms	2808 KiB

prize

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

int n, v[N], maior, ans, raiz;

int solve(int a, int b)
{
	int mid = (a + b)/2;

	int l = max(a + 1, mid - 250), r = min(b - 1, mid + 250);

	vector<int> esq = ask(a), dir = ask(b);

	if(esq[0] + esq[1] == 0) return a;

	if(dir[0] + dir[1] == 0) return b;

	if(b - a < 2) return -1;

	for(int p = l; p <= r; p++)
	{
		vector<int> aux = ask(p);

		if(aux[0] + aux[1] == 0) return p;

		if(aux[0] + aux[1] == maior)
		{
			int cnt_esq = aux[0] - esq[0];

			int cnt_dir = aux[1] - dir[1];

			int solve_esq = -1, solve_dir = -1;

			if(cnt_esq) solve_esq = solve(a, p);

			if(cnt_dir) solve_dir = solve(p, b);

			return max(solve_dir, solve_esq);
		}
	}
	return -2;
}

int find_best(int n)
{
	int st = 0, en = n - 1;

	 raiz = sqrt(n) + 1;

	for(int i = 0; i < 500; i++)
	{
		vector<int> aux = ask(i);

		if(aux[0] + aux[1] > maior)
		{
			maior = aux[0] + aux[1];

			st = i;
		}

		if(aux[0] + aux[1] == 0) return i;
	}

	for(int i = n - 1, cnt = 0; cnt < 500; cnt ++)
	{
		vector<int> aux = ask(i);

		if(aux[0] + aux[1] == maior)
		{
			en = i;

			break;
		}

		if(aux[0] + aux[1] == 0) return i;
	}

	return solve(st, en);

	int ini = 0, fim = n - 1, mid;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		vector<int> aux = ask(mid);

		if(aux[0] + aux[1] == 0) return mid;

		if(aux[0]) fim = mid - 1;

		else ini = mid + 1;
	}
}

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