Submission #1297782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297782		ChuanChen	Gap (APIO16_gap)	C++20	100 / 100	47 ms	3316 KiB

gap

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll INF=1e18;
#include "gap.h"

ll findGap(int T, int n){
	if(T==1){
		vector<ll>v(n);
		ll l=0, r=INF, idl=0, idr=n-1;
		while(idl<=idr){
			ll a=-1, b=-1;
			MinMax(l,r,&a,&b);
			l=a; r=b;
			v[idl]=l; v[idr]=r;
			l++; r--;
			idl++; idr--;
		}
		ll resp=0;
		for(int i=1;i<n;i++) resp=max(resp,v[i]-v[i-1]);
		return resp;
	}

	ll mn, mx, a1, an;
	MinMax(0, INF, &mn, &mx);
	if(n == 2) return mx-mn;
	a1 = mn; an = mx;
	ll A = mx-mn;
	ll B = A/(n-1);
	//[0, B] [B+1, 2B+1] .. 
	vector<pair<ll, ll>> intervals; 
	for(ll i = a1; i <= an; i+=B+1){
		ll l = i, r = i+B;
		MinMax(l, r, &mn, &mx);
		if(mn == -1) continue;
		intervals.emplace_back(mn, mx);
	}
	ll resp = 0;
	for(int i = 1; i < intervals.size(); i++){
		resp = max(intervals[i].first-intervals[i-1].second, resp);
	}
	return resp;
}

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