Submission #262126

#	Time	Username	Problem	Language	Result	Execution time	Memory
262126		define	Gap (APIO16_gap)	C++17	30 / 100	127 ms	1272 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 ans=0,now=mn,mxx=mx;
	for(int i=0;i<N-1;i++){
		int ok=0,ng=-1;
		while(now+(1ll<<ok)<=1e18)ok++;
		while(ok-ng>1){
			int mid=(ok+ng)/2;
			MinMax(now+1,now+(1ll<<mid),&mn,&mx);
			if(mn!=-1){
				chmax(ans,mn-now);
				now=mn;
				goto ok;
			}
			ng=mid;
		}
		MinMax(now+1,now+(1ll<<ok),&mn,&mx);
		chmax(ans,mn-now);
		now=mn;
		ok:;
	}
	chmax(ans,mxx-mn);
	return ans;
}
ll findGap(int T, int N){
	if(T==1)return solve1(N);
	return solve2(N);
}

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