제출 #1182440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182440		boclobanchat	Gap (APIO16_gap)	C++20	100 / 100	47 ms	3260 KiB

gap

#include"gap.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF=1e18;
long long findGap(int T,int N)
{
	if(T==1)
	{
		vector<long long> vi;
		long long mn=-1,mx=INF+1;
		for(int i=1;i<=(N+1)/2;i++)
		{
			long long l=mn,r=mx;
			MinMax(l+1,r-1,&mn,&mx);
			if(mn!=-1) vi.push_back(mn),vi.push_back(mx);
			else break;
		}
		sort(vi.begin(),vi.end());
		long long ans=0;
		for(int i=1;i<vi.size();i++) ans=max(ans,vi[i]-vi[i-1]);
		return ans;
	}
	else
	{
		long long mn,mx;
		MinMax(0,INF,&mn,&mx);
		if(N==2) return mx-mn;
		long long gap=mx-mn-1;
		vector<long long> vi;
		vi.push_back(mn),vi.push_back(mx);
		mn++;
		for(int i=0;i<N-2;i++)
		{
			long long a,b;
			MinMax(mn,mn+(gap+i)/(N-2)-1,&a,&b);
			if(a!=-1) vi.push_back(a),vi.push_back(b);
			mn+=(gap+i)/(N-2);
		}
		sort(vi.begin(),vi.end());
		long long ans=0;
		for(int i=1;i<vi.size();i++) ans=max(ans,vi[i]-vi[i-1]);
		return ans;
	}
}

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