Submission #1222379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222379		Joon_Yorigami	Gap (APIO16_gap)	C++17	100 / 100	43 ms	2668 KiB

gap

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

ll solveST1(ll n)
{
	vll arr;
	vll barr;
	ll mn,mx;
	ll p1=1;
	ll p2=n;
	ll lb=0;
	ll ub=1000000000000000000ll;
	while(p1<p2)
	{
		MinMax(lb,ub,&mn,&mx);
		arr.push_back(mn);
		barr.push_back(mx);
		lb=mn+1;
		ub=mx-1;
		p1+=1;
		p2-=1;
	}
	if(p1==p2)
	{
		MinMax(lb,ub,&mn,&mx);
		arr.push_back(mn);
	}
	reverse(barr.begin(),barr.end());
	for(auto num:barr)
		arr.push_back(num);
	ll ans=1;
	for(int i=1;i<n;i++)
		ans=max(ans,arr[i]-arr[i-1]);
	return ans;
}

ll solveST2(int n)
{
	ll ans=1;
	ll lb,ub;
	MinMax(1,1000000000000000000ll,&lb,&ub);
	ll l,r,mid;
	vll arr;
	ll m=1;
	l=2;r=(1000000000000000001ll+n)/(n-1);
	while(l<=r)
	{
		mid=l+(r-l)/2;
		ll val=lb+mid*(n-2);
		if(val>=ub||ub-val<mid)
		{
			r=mid-1;
			continue;
		}
		if(ub-val==mid)
		{
			m=mid;
			l=r+1;
		}
		else
		{
			m=mid+1;
			l=mid+1;
		}
	}
	ans=m;
	ll prev=lb;
	ll idx=lb-1;;
	ll mn,mx;
	while(1)
	{
		MinMax(idx+1,idx+1+m,&mn,&mx);
		idx=idx+1+m;
		if(mn==-1)
			continue;
		ans=max(ans,mn-prev);
		prev=mx;
		if(mx==ub)
			break;
	}
	return ans;
}

long long findGap(int T, int N)
{
	if(T==1)
		return solveST1(N);
	else
		return solveST2(N);
}

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