Submission #1194057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194057		nouka28	Gap (APIO16_gap)	C++20	70 / 100	51 ms	5220 KiB

gap

#include "gap.h"

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

long long findGap(signed T, signed N)
{
	int mn,mx;
	MinMax(1LL,1000000000000000000LL,&mn,&mx);

	if(N==2){
		return mx-mn;
	}

	int t=mx-mn-1;
	vector<int> d(N-2);
	for(auto&&e:d)e=t/(N-2);
	t-=accumulate(all(d),0LL);
	for(auto&&e:d)if(t){t--,e++;}

	vector<pair<int,int>> vs={{mn,mn+d[0]}};

	vector<int> a={mn,mx};

	rep(i,N-2){
		if(i){
			vs.push_back({vs.back().se+1,vs.back().se+1+d[i]});
		}
		auto[l,r]=vs.back();
		MinMax(l,r,&mn,&mx);
		if(mn==-1)continue;
		a.push_back(mn),a.push_back(mx);
	}

	sort(all(a));

	int ans=-1;
	rep(i,a.size()-1)ans=max(ans,a[i+1]-a[i]);

	return ans;
}

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