Submission #206214

#	Time	Username	Problem	Language	Result	Execution time	Memory
206214		mraron	Gap (APIO16_gap)	C++14	100 / 100	113 ms	9416 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll> res;
int n;

void solve1(ll L, ll R) {
	if((int)res.size()==n||L>R) return ;
	ll a,b;
	MinMax(L,R,&a,&b);
	if(a==-1) return ;
	res.insert(a);
	res.insert(b);
	solve1(a+1,b-1);
}	

void add(ll L, ll R) {
	if((int)res.size()==n||L>R) return ;
	ll a,b;
	MinMax(L,R,&a,&b);
	if(a==-1) return ;
	res.insert(a);
	res.insert(b);
}	

ll findGap(int T, int N)
{
	n=N;
	if(T==2) {
		ll mn,mx;
		MinMax(0, 1000000000000000000LL,&mn,&mx);
		ll val=(mx-mn+n-2)/(n-1);
		res.insert(mn);
		res.insert(mx);
		//cerr<<val<<"\n";
		for(int i=0;i<n-1;++i) {
			add(mn+i*val+1, mn+(i+1)*val);
		}
	}else {
		solve1(0, 1000000000000000000LL);
	}
	vector<ll> ans;
	for(auto i:res) ans.push_back(i);
	ll val=0;
	for(int i=1;i<(int)ans.size();++i) val=max(val, ans[i]-ans[i-1]);
	return val;
	
}

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