Submission #581738

#	Time	Username	Problem	Language	Result	Execution time	Memory
581738		alireza_kaviani	The Big Prize (IOI17_prize)	C++17	97.65 / 100	64 ms	1968 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;
mt19937 rng(8465374);

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 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) {
	fill(res + 1 , res + MAXN , pii(-1 , -1));
	for(int i = 0 ; i < 500 ; i++){
		pii cnt = query(rng() % n + 1);
		mx = max(mx , cnt.X + cnt.Y);
	}
	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 solve(int, int)':
prize.cpp:30:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  if(A.X + A.Y == mx && A.X == ans.size()){
      |                        ~~~~^~~~~~~~~~~~~
prize.cpp:37:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |  int mid = l + r >> 1;
      |            ~~^~~

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