Submission #38406

# Submission time Handle Problem Language Result Execution time Memory
38406 2018-01-04T05:17:52 Z MatheusLealV The Big Prize (IOI17_prize) C++14
0 / 100
23 ms 2796 KB
#include <bits/stdc++.h>
#define N 200050
#include "prize.h"
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 - 300), r = min(b - 1, mid + 300);
 
	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);
		}
	}
 
	//cout<<"HERE\n";
	return -2;
}
 
int find_best(int n)
{
	int st = 0, en = n - 1, raiz = 500;
 
	for(int i = 0; i < raiz; i++)
	{
		vector<int> aux = ask(i);
 
		if(aux[0] + aux[1] > maior)
		{
			maior = aux[0] + aux[1];
 
			st = i;
		}
	}
 
	for(int i = n - 1, cnt = 0; cnt < raiz; cnt ++)
	{
		vector<int> aux = ask(i);
 
		if(aux[0] + aux[1] == maior)
		{
			en = i;
 
			break;
		}
	}
 
	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;
	}
}
# Verdict Execution time Memory Grader output
1 Correct 6 ms 2796 KB Output is correct
2 Correct 9 ms 2796 KB Output is correct
3 Correct 6 ms 2796 KB Output is correct
4 Correct 13 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Incorrect 13 ms 2796 KB Integer -1 violates the range [0, 199999]
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 2796 KB Integer -1 violates the range [0, 199999]
2 Halted 0 ms 0 KB -