Submission #405691

#	Time	Username	Problem	Language	Result	Execution time	Memory
405691		inluminas	Gap (APIO16_gap)	C++14	12.89 / 100	74 ms	2236 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define endl "\n"

vector<ll>a;

void f(ll L,ll R){
	if(R<L) return;
	ll mn,mx;
	MinMax(L,R,&mn,&mx);
	if(mn==-1) return;
	if(mn==mx){
		a.push_back(mn);
		return;
	}
	a.push_back(mn);
	a.push_back(mx);
	if(mn+1==mx) return;
	mn++,mx--;
	ll mid=(mn+mx)/2;
	if(mn<=mid) f(mn,mid);
	if(mid<mx) f(mid+1,mx);
}

long long findGap(int T, int N)
{

	f(0,1e18);

	sort(a.begin(),a.end());
	a.resize(unique(a.begin(),a.end())-a.begin());
	ll res=0;
	for(int i=1;i<N;i++){
		res=max(res,a[i]-a[i-1]);
	}

	return res;
}

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