Submission #1194064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194064		nouka28	Gap (APIO16_gap)	C++20	100 / 100	49 ms	5216 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)
{

	if(T==1){
		int mn=1LL,mx=1000000000000000000LL;
		
		vector<int> a;
		rep(i,(N+1)/2){
			int l=mn,r=mx;
			MinMax(l,r,&mn,&mx);
			a.push_back(mn);
			if(mn!=mx)a.push_back(mx);
			mn++,mx--;
		}

		sort(all(a));
		int ans=-1;
		rep(i,N-1)ans=max(ans,a[i+1]-a[i]);
		return ans;
	}

	if(T==2){
		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;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
   73 | }
      | ^

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