Submission #390479

#	Time	Username	Problem	Language	Result	Execution time	Memory
390479		alireza_kaviani	The Big Prize (IOI17_prize)	C++11	97.11 / 100	69 ms	1880 KiB

prize

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

typedef pair<int, int> pii;

#define X		first
#define Y		second

const int MAXN = 2e5 + 10;

int cnt , mx;
pii res[MAXN];

pii get(int x){
	if(res[x].X != -1)	return res[x];
	vector<int> vec = ask(x);
	res[x] = {vec[0] , vec[1]};
	return res[x];
}

int solve(int l , int r){
	pii cur = get(r - 1);
	if(cur.X + cur.Y == mx && cur.X <= cnt)	return -1;
	if(r - l == 1){
		cnt++;
		if(cur.X + cur.Y == 0)	return l;
		return -1;
	}
	int mid = l + r >> 1;
	int ans = solve(l , mid);
	if(ans == -1)	return solve(mid , r);
	return ans;
}

int find_best(int n) {
	fill(res , res + MAXN , pii(-1 , -1));
	for(int i = 0 ; i < min(530 , n) ; i++){
		pii x = get(i);
		mx = max(mx , x.X + x.Y);
	}
	return solve(0 , n);
}

Compilation message (stderr)

prize.cpp: In function 'int solve(int, int)':
prize.cpp:30:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int mid = l + r >> 1;
      |            ~~^~~

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