Submission #1315815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315815		wangzhiyi33	Gap (APIO16_gap)	C++20	100 / 100	46 ms	1980 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long 

ll n,ans;

ll solve(){
	ll apa[n+1];
	ll mn,mx;
	MinMax(0,1e18,&mn,&mx);
	apa[1]=mn,apa[n]=mx;

	for(int l=2,r=n-1;l<=r;l++,r--){
		mn++,mx--;
		MinMax(mn,mx,&mn,&mx);
		apa[l]=mn,apa[r]=mx;
	}

	ll ans=0;
	for(int q=1;q<n;q++){
		ans=max(ans,apa[q+1]-apa[q]);
	}
	return ans;
}


ll findGap(int T, int N){
	n=N;

	if(T==1){
		return solve();
	}

	ll mn,mx;
	MinMax(0,1e18,&mn,&mx);

	ll grup=(mx-mn+n-2)/(n-1);
	ans=grup;
	
	ll satu,dua,lst;
	lst=mn;

	for(satu=mn+1,dua=mn+grup;satu<=mx;satu+=grup,dua+=grup){
		dua=min(dua,mx);
		ll apa1,apa2;
		MinMax(satu,dua,&apa1,&apa2);
		if(apa1==-1)continue;
		ans=max(ans,apa1-lst);
		lst=apa2;
	}
	
	return ans;
}

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