Submission #1239679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239679		mychecksedad	The Big Prize (IOI17_prize)	C++20	20 / 100	36 ms	6612 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define vi vector<int>
#define all(x) x.begin(),x.end()
const int N = 4e5+100, M = 1e9;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rn(int l, int r){
	return uniform_int_distribution<int>(l,r)(rng);
}


int n, T[2*N+5], sum = 0, summ;
void build(int sz){
	for(int j = 0; j <= 2*sz + 5; ++j) T[j] = 0;
}
void upd(int p, int val){
	++p;
	p += n;
	T[p]++;
	for(p >>= 1; p; p >>= 1) T[p] = T[p<<1] + T[p<<1|1]; 
}
int get(int l, int r){
	int res = 0;
	l += n + 1;
	r += n + 2;
	for(; l < r; l >>= 1, r >>= 1){
		if(l&1) res += T[l++];
		if(r&1) res += T[--r];
	}
	return res;
}
set<pii> X, Y;
int qq = 0;
pair<bool, pair<vi, vi>> askk(int x){
	qq++;
	bool flag = false;
	if(qq > 9500) assert(false);
	vi res = ask(x);
	if(res[0] + res[1] == 0) return {flag, {{-M, -M}, {-M, -M}}};
	if(res[0] + res[1] == summ) flag = true;
	vi ress = res;
	Y.insert({x, res[1]});
	res[0] -= get(0, x - 1);
	res[1] -= get(x + 1, n - 1);
	return {flag, pair<vi,vi>{res, ress}};
}
int solve(vi &v){
	if(v.empty()) return -1;
	int mid = (int)v.size()/2;
	int pt = v[mid];
	vi q;
	q.pb(v[mid]);
	for(int j = 1; j < mid + 5; ++j){
		if(mid - j >= 0) q.pb(v[mid - j]);
		if(mid + j < (int)v.size()) q.pb(v[mid + j]);
	}
	bool fine = false;
	vi resmid, resmidd;
	int mmid;
	vi L, R;
		// for(int x: q) cerr << x << ' ';
		// 	cerr << '\n';
	for(int x: q){
		if(fine){
			if(x > mmid) R.pb(x);
			else L.pb(x);
			continue;
		}
		auto p = askk(x);
		bool flag = p.ff;
		vi res = p.ss.ff;
		vi res2 = p.ss.ss;
		if(res[0] == -M) return x;
		if(flag){
			// we can split now..
			fine = true;
			resmid = res;
			resmidd = res2;
			mmid = x;
		}else{
			upd(x, 1);
			--sum; // decrease sum
		}
	}
	if(!fine){
		// none  here lol
		return -1;
	}


	sort(all(R));
	sort(all(L));

	int id = v.back();

	auto it = Y.lower_bound(pii{id, M});
	if(it != Y.end()){
		resmid[1] = resmidd[1] - (*it).ss - get(mmid + 1, (*it).ff);
		// resmid[1] -= ((*it).ss - get((*it).ff + 1, n - 1));
	}
	
	if(resmid[0] > 0){
		int x = solve(L);
		if(x != -1) return x;
	}

	if(resmid[1] > 0){
		assert(R.size());
		int x = solve(R);
		if(x != -1) return x;
	}

	return -1;
}


int find_best(int nn) {
	n = nn;
	build(n);
	for(int j = 0; j < 50; ++j){
		int pt = rn(0, n-1);
		
		auto p = askk(pt);
		bool flag = p.ff;
		vi res = p.ss.ff;
		vi res2 = p.ss.ss;
		if(res[0] == -M) return pt; 
		if(sum < res[0] + res[1])
			sum = res[0] + res[1];
	}

	vi v;
	for(int j = 0; j < n; ++j) v.pb(j);

	summ = sum;

	return solve(v);
}

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