Submission #1152304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152304		zhasyn	Gap (APIO16_gap)	C++20	100 / 100	36 ms	5152 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
// void MinMax(ll l, ll r, ll &mn, ll &mx){
// 	cout << l <<" " << r << endl;
// 	cin >> mn >> mx;
// }
vector <ll> vec;
int nx;
void calc(ll l, ll r){
	ll mn, mx;
	MinMax(l, r, &mn, &mx);
	if(mn == -1) return;
	if(mn == mx){
		vec.pb(mn);
		return;
	}
	vec.pb(mn);
	vec.pb(mx);
	l = mn + 1;
	r = mx - 1;
	if((ll)vec.size() == nx) return;
	calc(l, r);
}
long long findGap(int t, int n)
{
	nx = n;
	ll ans = 1;
	if(t == 1){
		calc(0, 1e18);
		sort(vec.begin(), vec.end());
		for(ll i = 0; i < (ll)vec.size() - 1; i++){
			ans = max(ans, vec[i + 1] - vec[i]);
		}
	} else{
		ll mn, mx, gr = (n - 1) / 2, prev, k, l = 0, r = 1e18;
		MinMax(l, r, &mn, &mx);
		if(n == 2) return mx - mn;
		prev= mn;
		l = mn + 1;
		r = mx - 1;
		k = (r - l + 1) / gr;
		for(ll cur = l; cur <= r; cur = cur + k){
			ll mnx, mxx;
			MinMax(cur, min(cur + k - 1, r), &mnx, &mxx);
			if(mnx != -1){
				ans = max(ans, mnx - prev);
				ans = max(ans, mxx - mnx);
				prev = mxx;
			}
		}
		ans = max(ans, mx -prev);
	}
	return ans;
}



// int main(){
//   	ios::sync_with_stdio(false);
//   	cin.tie(NULL);
//   	ll t, n;
//   	cin >> t >> n;
//   	findGap(t, n);
//   return 0;
// }

 

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