#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mn, mx;
ll st1(int n) {
ll s = 0, t = 1e18;
MinMax(s, t, &mn, &mx);
ll ans = 0;
for (ll i = 2; i <= n / 2; i++) {
ll pmn = mn, pmx = mx;
MinMax(mn + 1, mx - 1, &mn, &mx);
ans = max(ans, mn - pmn);
ans = max(ans, pmx - mx);
}
if (n % 2 == 1) {
ll fin, fin2;
MinMax(mn + 1, mx - 1, &fin, &fin2);
ans = max(ans, fin - mn);
ans = max(ans, mx - fin);
} else {
ans = max(ans, mx - mn);
}
return ans;
}
ll st2(int n) {
/*
Solution outline:
Query(0, 1e18) -> n + 1 queries
n - 2 items left, given a[1] and a[n]
Idea:
spilt the range into n - 1
by pigeonhole principle, at least 1 range has no items
(and there definitely exists a range which is >= that range)
Take max(min of right range - max of left range)
*/
ll s = 0, t = 1e18;
MinMax(s, t, &mn, &mx);
s = mn + 1; t = mx - 1;
ll range = (t - s) + 1;
range /= (n - 1);
// fprintf(stderr, "Range: %lld\n", range);
ll int rs = s, rt = s + range - 1;
ll int prev = mn;
ll int ans = 0;
for (int i = 0; i < n - 2; i++) {
MinMax(rs, rt, &mn, &mx);
// fprintf(stderr, "Query: %lld %lld, return: %lld %lld\n", rs, rt, mn, mx);
rs += range; rt += range;
if (mn == -1) continue;
ans = max(ans, mn - prev);
prev = mx;
}
MinMax(rs, t, &mn, &mx);
// fprintf(stderr, "[FINAL] Query: %lld %lld, return: %lld %lld\n", rs, t, mn, mx);
if (mn != -1) {
ans = max(ans, mn - prev);
ans = max(ans, (t + 1) - mx);
} else {
ans = max(ans, (t + 1) - prev);
}
return ans;
}
long long findGap(int T, int N) {
if (T == 1) return st1(N);
else return st2(N);
}
