Submission #390482

#	Time	Username	Problem	Language	Result	Execution time	Memory
390482		alireza_kaviani	The Big Prize (IOI17_prize)	C++11	100 / 100	73 ms	1996 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;
}

void find_mx(int n){
	int cnt = 530;
	queue<pii> q;
	q.push({0 , n});
	while(!q.empty()){
		int l = q.front().X , r = q.front().Y; q.pop();
		if(res[r - 1].X == -1)	cnt--;
		mx = max(mx , get(r - 1).X + get(r - 1).Y);
		if(cnt == 0)	break;
		if(r - l == 1)	continue;
		int mid = l + r >> 1; 
		q.push({l , mid});
		q.push({mid , r});
	}
}

int find_best(int n) {
	fill(res , res + MAXN , pii(-1 , -1));
	find_mx(n);
	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;
      |            ~~^~~
prize.cpp: In function 'void find_mx(int)':
prize.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid = l + r >> 1;
      |             ~~^~~

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