Submission #145241

#	Time	Username	Problem	Language	Result	Execution time	Memory
145241		dennisstar	Gap (APIO16_gap)	C++11	100 / 100	78 ms	2416 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll ar[100010]; int tp;
ll mx, mn, gp;
priority_queue<ll, vector<ll>, greater<ll> > pq;
long long findGap(int T, int N)
{
	if (T==1) {
		mn=-1, mx=1000000000000000000ll+1ll;
		int cnt=0;
		for (int j=0; j<(N+1)/2; j++) {
			if (mn+1>mx-1) break;
			MinMax(mn+1, mx-1, &mn, &mx);
			pq.push(mn); pq.push(mx);
			cnt++;
		}
		gp=pq.top(); pq.pop();
		mx=0;
		while (!pq.empty()) {
			mn=gp; gp=pq.top(); pq.pop();
			mx=max(mx, gp-mn);
		}
		return mx;
	}
 	MinMax(0, 1000000000000000000ll, &mn, &mx);
	gp=(mx-mn+N-2)/(ll)(N-1);
	ll n, x;
	for (ll i=mn; i<mx; i+=gp) {
		MinMax(i, min(i+gp-1, mx-1), &n, &x);
		if (n==-1&&x==-1) continue;
		if (n==x) ar[tp++]=n;
		else {
			ar[tp++]=n; ar[tp++]=x;
		}
	}
	ar[tp++]=mx;
	ll ans=0;
	for (int j=0; j<tp-1; j++) ans=max(ans, ar[j+1]-ar[j]);
	return ans;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70