# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1150768 | zhasyn | Gap (APIO16_gap) | C++20 | 0 ms | 0 KiB |
#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;
}