Submission #1137405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137405		owoovo	Gap (APIO16_gap)	C++20	70 / 100	44 ms	3260 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
#define ll long long
#define F first 
#define S second 
using namespace std;
const ll maxn=1e18;
ll findGap(int T, int N){
	vector<ll> hv;
	ll mn, mx;
	MinMax(0,maxn,&mn,&mx);
	hv.push_back(mn);
	hv.push_back(mx);
	if(N==2){
		return mx-mn;
	}
	ll U=(mx)-1,D=(mn)+1,k=N;
	ll cnt=(U-D+1)/k,t=(U-D+1)%k;
	//cout<<U<<" "<<D<<" "<<k<<" "<<cnt<<" "<<t<<"\n";
	for(int i=0;i<k-t;i++){
		if(cnt==0)continue;
		// cout<<D+i*cnt<<" "<<D+(i+1)*cnt-1<<"\n";
		MinMax(D+i*cnt,D+(i+1)*cnt-1,&mn,&mx);
		if((mn)!=-1)hv.push_back(mn);
		if((mx)!=-1)hv.push_back(mx);
	}
	ll DD=D+(k-t)*cnt;
	for(int i=0;i<t;i++){
		// cout<<DD+i*(cnt+1)<<" "<<DD+(i+1)*(cnt+1)-1<<"\n";
		MinMax(DD+i*(cnt+1),DD+(i+1)*(cnt+1)-1,&mn,&mx);
		if((mn)!=-1)hv.push_back(mn);
		if((mx)!=-1)hv.push_back(mx);
	}
	sort(hv.begin(),hv.end());
	hv.erase(unique(hv.begin(),hv.end()),hv.end());
	ll ans=0;
	for(int i=1;i<hv.size();i++){
		ans=max(ans,hv[i]-hv[i-1]);
	}
	return ans;
}

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