Submission #1150770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150770		zhasyn	Gap (APIO16_gap)	C++20	12.76 / 100	58 ms	3260 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 int  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;
vector <ll> vec;
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;
	ll mid = (r + l) / 2;
	if(l <= mid) calc(l, mid);
	if(mid <= r) calc(mid, r);
}
long long findGap(int t, int n)
{
	calc(0, 1e18);
	sort(vec.begin(), vec.end());
	ll ans = 1;
	for(ll i = 0; i < (ll)vec.size() - 1; i++){
		ans = max(ans, vec[i + 1] - vec[i]);
	}
	return ans;
}



 

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