Submission #1269115

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

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long findGap(int T, int N)
{
	if(T==1){
		int n=N;
		vector<ll> v(n);
		MinMax(0ll, (ll)1e18, &v[0], &v[n-1]);
		for(int i=1;i<=(n-1)/2;i++){
			MinMax(v[i-1]+1, v[n-i]-1, &v[i], &v[n-i-1]);
		}
		ll ans=0;
		for(int i=0;i<n-1;i++){
			ans=max(ans, v[i+1]-v[i]);
		}
		return ans;
	}
	else if(T==2){
		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;
	}
}

Compilation message (stderr)

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

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