Submission #140844

#	Time	Username	Problem	Language	Result	Execution time	Memory
140844		tmwilliamlin168	The Big Prize (IOI17_prize)	C++14	100 / 100	53 ms	1484 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=2e5;
int n, a, ft[mxN+1];
vector<int> v;
bool d[mxN];

void upd(int i) {
	for(++i; i<=n; i+=i&-i)
		++ft[i];
}

int qry(int i) {
	int r=0;
	for(; i; i-=i&-i)
		r+=ft[i];
	return r;
}

int dc(int l=0, int r=n-1, int sl=0, int sr=a) {
	if(l>r)
		return -1;
	int ml=(l+r)/2, mr=ml+1, t=0;
	vector<int> b;
	while(1) {
		//cout << l << " " << r << " " << sl << " " << sr << " " << ml << " " << mr << endl;
		if(qry(r+1)-qry(l)>=sr-sl)
			return -1;
		int m=t?mr++:ml--;
		t^=1;
		if(d[m])
			continue;
		b=ask(m);
		int c=b[0]+b[1];
		if(!c)
			return m;
		if(c>a) {
			a=c;
			for(int vi : v) {
				d[vi]=1;
				upd(vi);
			}
			v.clear();
			return dc();
		}
		if(c==a) {
			v.push_back(m);
			if(t) {
				b[1]=b[0]+(mr-ml-2);
			} else {
				b[1]=b[0];
				b[0]-=(mr-ml-2);
			}
			break;
		}
		if(c<a) {
			d[m]=1;
			upd(m);
		}
	}
	int rl=dc(l, ml, sl, b[0]), rr=-1;
	//cout << "g " << l << " " << r << " " << sl << " " << sr << " " << rl << endl;
	if(rl<0)
		rr=dc(mr, r, b[1], sr);
	return max(rl, rr);
}

int find_best(int N) {
	n=N;
	vector<int> b=ask(n-1);
	a=b[0]+b[1];
	return a?dc():n-1;
}

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