제출 #1239641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239641		mychecksedad	커다란 상품 (IOI17_prize)	C++20	20 / 100	49 ms	7140 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 = 2e5+100;

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;
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;
}
int qq = 0;
vi askk(int x){
	qq++;
	if(qq > 9500) assert(false);
	vi res = ask(x);
	if(res[0] + res[1] == 0) return {-N, -N};
	res[0] -= get(0, x - 1);
	res[1] -= get(x + 1, n - 1);
	return res;
}
set<pii> X, Y;
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;
	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;
		}
		vi res = askk(x);
		if(res[0] == -N) return x;
		if(res[0] + res[1] == sum){
			// we can split now..
			fine = true;
			resmid = res;
			mmid = x;
		}else{
			upd(x, 1);
			--sum; // decrease sum
		}
	}
	if(!fine){
		// none  here lol
		return -1;
	}


	sort(all(R));
	sort(all(L));
	fine = false;

	vi resright;
	reverse(all(R));
	vi RR;
	for(int x: R){
		if(fine){
			RR.pb(x);
			continue;
		}
		vi res = askk(x);
		// cerr << x << ' ' ;
		if(res[0] == -N) return x;
		if(res[0] + res[1] == sum){
			// we can split now..
			fine = true;
			resright = res;
		}else{
			upd(x, 1);
			--resmid[1];
			--sum; // decrease sum
		}
	}
	sort(all(RR));

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

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

	return -1;
}


int find_best(int nn) {
	n = nn;
	build(n);
	for(int j = 0; j < 40; ++j){
		int pt = rn(0, n-1);
		vi res = askk(pt);
		if(res[0] == -N) 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);


	return solve(v);
}

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