Submission #423911

#	Time	Username	Problem	Language	Result	Execution time	Memory
423911		Rudy420	The Big Prize (IOI17_prize)	C++17	100 / 100	93 ms	1944 KiB

prize

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define lg length()
#define pb push_back
#define INF 2000000005
#define LINF 1000000000000000005
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
#include "prize.h"

vector<int> l,r;
vector<int> res;
int found = 0, mx = 0;

void Qry(int p){
	if(l[p] != -1) return;
	res = ask(p);
	l[p] = res[0]; r[p] = res[1];
}

void BS(int L, int R){
	if(found) return;
	if(R-L < 2) return;
	if(l[L] == l[R] && l[L] == l[R]) return;
	if(l[L] == 0 && r[L] == 0) found = 1;

	int M = (L+R)/2;
	Qry(M);
	if(l[M] + r[M] != l[L] + r[L] && l[M] + r[M] != l[L] + r[L] && M - 1 > L){
		M--;
		Qry(M);
		if(l[M] + r[M] != l[L] + r[L] && l[M] + r[M] != l[L] + r[L] && M + 2 < R){
			M+=2;
			Qry(M);
		}
	}

	BS(L, M);
	BS(M, R);
}

int find_best(int n) {
	l.resize(n, -1);
	r.resize(n, -1);

	Qry(0); Qry(n-1);

	BS(0, n-1);

	for(int i=0;i<n;i++){
		if(l[i] == 0 && r[i] == 0) return i;
	}
	
	return 0;
}

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