Submission #1319521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319521		husseinjuanda	Gap (APIO16_gap)	C++20	70 / 100	39 ms	2332 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

long long findGap(int T, int n)
{
	if(T == 1){
		ll ns = 0;
		ll l = 0;
		ll r = 1e18;
		vector<ll> ar;
		while(l <= r){
			if(ar.size() > n) break;
			ll mn = 0;
			ll mx = 0;
			MinMax(l, r, &mn, &mx);
			if(mn == -1) break;
			ar.push_back(mn);
			ar.push_back(mx);
			l = mn+1;
			r = mx-1;
		}
		sort(ar.begin(), ar.end());
		for(int i = 1; i < ar.size(); i++){
			ns = max(ns, ar[i] - ar[i-1]);
		}
		return ns;
	}
	ll mn = 0;
	ll mx = 0;
	MinMax(0, 1e18, &mn, &mx);
	ll l = mn;
	ll r = mx;
	ll pgh = (mx - mn)/(n-1);
	if((mx - mn)%(n-1) != 0){
		pgh++;
	}
	pgh--;
	// cout << pgh << endl;
	ll cur = l+1;
	ll lst = l;
	ll ns = 0;
	while(cur <= r){
		if(cur == r){
			mx = max(mx, r-lst);
			break;
		}
		//cur, cur + pgh	
		MinMax(cur, min(cur+pgh, r), &mn, &mx);
		cur += pgh+1;
		if(mn == -1) continue;
		ns = max(ns, mn-lst);
		lst = mx;
	}
	return ns;
}



// 2 3 4 5 6 7 8

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