Submission #262143

#	Time	Username	Problem	Language	Result	Execution time	Memory
262143		define	Gap (APIO16_gap)	C++17	100 / 100	85 ms	1276 KiB

gap

#include "gap.h"
#define ll long long

#include<iostream>
using namespace std;

template<class T>
inline bool chmax(T &a,T b){
	if(a<b){a=b;return true;}
	return false;
}
ll solve1(int N){
	ll ans=0;
	ll l=-1,r=1e18;r+=1;
	for(int i=0;i<(N+1)/2;i++){
		ll mn,mx;
		MinMax(l+1,r-1,&mn,&mx);
		if(i){
			chmax(ans,mn-l);
			chmax(ans,r-mx);
		}
		l=mn;
		r=mx;
	}
	if(N%2==0)chmax(ans,r-l);
	return ans;
}
ll solve2(int N){
	ll mn,mx;
	MinMax(0,1e18,&mn,&mx);
	ll sz=(mx-mn+N-1)/N;
	ll l=mn+1,r=mn+sz,now=mn;
	ll ans=0;
	for(int i=0;i<N;i++){
		MinMax(l,r,&mn,&mx);
		if(mn!=-1){
			chmax(ans,mn-now);
			now=mx;
		}
		l+=sz;r+=sz;
	}
	return ans;
}
ll findGap(int T, int N){
	if(T==1)return solve1(N);
	return solve2(N);
}

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