Submission #581753

#	Time	Username	Problem	Language	Result	Execution time	Memory
581753		alireza_kaviani	The Big Prize (IOI17_prize)	C++17	100 / 100	68 ms	1952 KiB

prize

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

typedef pair<int, int> pii;

#define X		first
#define Y		second
#define sep		' '

const int MAXN = 2e5 + 10;

int n , mx;
pii res[MAXN];
vector<int> ans;

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

void findMx(){
	int cnt = 0;
	queue<pii> Q;
	Q.push({0 , n});
	while(!Q.empty()){
		pii A = Q.front(); Q.pop();
		int l = A.X , r = A.Y;
		if(res[r] == pii(-1 , -1)){
			cnt++;
			query(r);
		}
		mx = max(mx , res[r].X + res[r].Y);
		if(cnt >= 500){
			return;
		}
		if(r - l == 1){
			continue;
		}
		int mid = l + r >> 1;
		Q.push({l , mid});
		Q.push({mid , r});
	}
}

void solve(int l , int r){ // (l , r]
	pii A = query(r);
	if(A.X + A.Y == mx && A.X == ans.size()){
		return;
	}
	if(r - l == 1){
		ans.push_back(r);
		return;
	}
	int mid = l + r >> 1;
	solve(l , mid);
	solve(mid , r);
}

int find_best(int N) {
	n = N;
	fill(res + 1 , res + MAXN , pii(-1 , -1));
	findMx();
	solve(0 , n);
	for(int i : ans){
		pii A = query(i);
		if(A.X + A.Y == 0){
			return i - 1;
		}
	}
	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'void findMx()':
prize.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid = l + r >> 1;
      |             ~~^~~
prize.cpp: In function 'void solve(int, int)':
prize.cpp:53:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  if(A.X + A.Y == mx && A.X == ans.size()){
      |                        ~~~~^~~~~~~~~~~~~
prize.cpp:60:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |  int mid = l + r >> 1;
      |            ~~^~~

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