Submission #1269108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269108		WH8	Gap (APIO16_gap)	C++20	70 / 100	41 ms	3256 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long findGap(int T, int N)
{
	ll a1, an;
	MinMax(0ll, (long long)1e18, &a1, &an);
	ll lb=(an-a1)/(N-1) + ((an-a1)%(N-1)==0?0:1);
	ll ans=lb;
	
	vector<pair<ll,ll>> v;
	for(ll l=a1;l<an;l+=lb){
		ll a, b;
		MinMax(l, l+lb-1, &a, &b);
		//~ printf("q %lld %lld: ret %lld %lld\n", l, l+lb-1, a, b);
		if(a!=-1)v.push_back({a, b});
	}
	v.push_back({an, an});
	for(int i=0;i<(int)v.size();i++){
		ans=max(ans, v[i].second-v[i].first);
		if(i < (int)v.size()-1)ans=max(ans, v[i+1].first-v[i].second);
	}
	return ans;
}

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