Submission #1243015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243015		mychecksedad	The Big Prize (IOI17_prize)	C++20	98.04 / 100	36 ms	8148 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 cerr if(false) cerr
#define ss second
#define vi vector<int>
#define all(x) x.begin(),x.end()
const int N = 4e5+100, M = 100000000;

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 = -37;
void build(int sz){
	for(int j = 0; j <= 2*sz + 5; ++j) T[j] = 0;
}
void upd(int p, int val){
	++p;
	while(p <= n){
		T[p]++;
		p += p&(-p);
	}
}
int get(int l, int r){
	if(l > r) return 0;
	++l, ++r;
	int res = 0;
	--l;
	while(l > 0){
		res -= T[l];
		l -= l&(-l);
	}
	while(r > 0){
		res += T[r];
		r -= r&(-r);
	}
	return res;
}

void assertt(bool x){
	if(!x){
		cerr <<" failn" << endl;
		vector<int> v;
			for(int j = 0; j < 1000000000; ++j){
				v.push_back(j);
			}
	}
}

set<pii> X, Y;
int qq = 0;
pair<bool, pair<vi, vi>> askk(int x, bool is){
	qq++;
	bool flag = false;
	if(qq > 9900) 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;
	if(is && flag){
		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()) assertt(false);
	for(int x: v) cerr << x << ' ';
	cerr << '\n';
	cerr << '\n';
	int mid = (int)v.size()/2;
	int pt = v[mid];
	vi q;
	q.pb(v[mid]);
	for(int j = 1; j < mid + 15; ++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, true);
		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 -2;
	}


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

	int id = v.back();

	// reverse(all(R));

	// vi RR;
	// fine = false;
	// for(int x: R){
	// 	if(fine){
	// 		RR.pb(x);
	// 		continue;
	// 	}

	// 	auto p = askk(x, true);
	// 	bool flag = p.ff;
	// 	vi res = p.ss.ff;
	// 	vi res2 = p.ss.ss;
	// 	if(res[0] == -M) return x;
	// 	if(flag){
	// 		fine = true;
	// 		resmid[1] -= res[1];
	// 	}else{
	// 		upd(x, 1);
	// 	}
	// }
	// R = RR;
	// sort(all(R));

	auto it = Y.lower_bound(pii{id, M});

	// cerr << id << ' ' << resmidd[1] << ' ';
	if(it != Y.end()){
		// cerr << (*it).ff << ' ' << (*it).ss << ' ' << get(mmid + 1, (*it).ff) << " creep ";
		resmid[1] = resmidd[1] - (*it).ss - get(mmid + 1, (*it).ff);
		// resmid[1] -= ((*it).ss - get((*it).ff + 1, n - 1));
	}else{
		resmid[1] = resmidd[1] - get(mmid + 1, n - 1);
	}


	cerr << mmid << ' ' << resmid[0] << ' ' << resmid[1] << " f\n";

	
	if(resmid[0] > 0){
		int x = solve(L);
		if(x != -2) return x;
	}

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

	return -2;
}


int find_best(int nn) {
	n = nn;
	build(n);
	vector<array<int, 3>> RES;
	for(int j = 0; j < 460; ++j){
		int pt = rn(0, n-1);
		
		auto p = askk(pt, false);
		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];
		RES.pb({res[0] + res[1], pt, res[1]});
	}
	for(auto [s, pt, y]: RES){
		if(s == sum){
			Y.insert({pt, y});
		}
	}

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

	summ = sum;

	return solve(v);
}

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