Submission #432176

#	Time	Username	Problem	Language	Result	Execution time	Memory
432176		jeroenodb	The Big Prize (IOI17_prize)	C++14	20 / 100	108 ms	11076 KiB

prize

#ifndef GRADER
#include "prize.h"
#endif
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
map<int,vi> qs;
vi test(int i) {
	if(qs.count(i)) return qs[i];
	else return qs[i] = ask(i);
}
template<typename T> struct fenwick {
	int n;
	vector<T> fen;
	fenwick(){}
	fenwick(int nn) {
		fen.resize(nn+1);
		n = nn;
	}
	auto sum(int i) {
		T ans = 0;
		while(i) {
			ans+=fen[i];
			i&=i-1;
		}
		return ans;
	}
	auto query(int l, int r) {
		return sum(r+1)-sum(l);
	}
	void update(int i, T val) {
		++i;
		while(i<=n) {
			fen[i]+=val;
			i+= i&(-i);
		}
	}
};
int worst(int i, int k) {
	if(k==0) return i;
	if(i==0) return 0;
	return worst(sqrt(i-1),k-1);
}
int find_best(int n) {
	int mx=0;
	for(int i=1;i<=4;++i) mx+=worst(n,i);
	int step = max(1,n/mx);
	int lolly=0;
	for(int i=0;i<n;i+=step) {
		auto v = test(i);
		lolly = max(lolly,v[0]+v[1]);
		if(lolly*lolly+1>worst(n,1)) break;
	}
	int left=lolly;
	set<int> cand;
	fenwick<int> fen(n);
	for(int i=0;i<n;++i) cand.insert(i);
	while(left--) {
		int lo=0,hi=n-1;
		while(lo<=hi) {
			int mid = int(lo*0.52+hi*0.48);
			auto it = cand.lower_bound(mid);
			if(it==cand.end() or *it>hi) {
				hi=mid-1;
				continue;
			}
			auto check = *it;
			auto v = test(check);
			if(v[0]+v[1]==lolly) {
				if(v[0]>fen.query(0,check)) {
					hi = mid-1;
				} else lo = mid+1;
			} else {
				if(v[0]+v[1]==0) return check;
				cand.erase(check);
				fen.update(check,1);
				break;
			}
		}

	}
	return 0;
}

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