제출 #286375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286375		egekabas	커다란 상품 (IOI17_prize)	C++14	0 / 100	18 ms	11756 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
vector<int> cur, nxt;
int ans = -1;
int curval;
vector<int> dp[200009];
int qu = 0;
vector<int> q(int x){
	if(dp[x].size())
		return dp[x];
	++qu;
	assert(qu <= 10000);
	return dp[x] = ask(x);
}
void binsearch(int l, int r, int lval, int rval){
	int cnt = curval-lval-rval;
	if(cnt <= 0) return;
	vector<int> v;
	for(int i = l; i <= r; ++i)
		v.pb(i);
	random_shuffle(all(v));
	for(auto u : v){
		if(ans != -1) return;;
		vector<int> res = q(cur[u]);
		if(res[0]+ res[1] == 0){
			ans = u;
			return;
		}
		if(res[0]+res[1] == curval){
			binsearch(l, u-1, lval, res[1]);
			binsearch(u+1, r, res[0], rval);
			return;
		}
	}
}
int find_best(int n) {
	srand(time(NULL));
	if(n <= 10000){
		for(int i = 0; i < n; ++i){
			vector<int> res = q(i);
			if(res[0]+res[1] == 0)
				return i;
		}
	}
	int times = 5;
	while(times--){
		int id = rand()%n;
		curval = max(curval, q(id)[0]+q(id)[1]);
	}
	binsearch(0, n-1, 0, 0);
	return ans;
}

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