#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back
void solve_t2(vll& nums, ll l, ll r, ll N) {
if(((ll)nums.size()) >= N) return;
if(r - l + 1ll <= 0ll) return;
ll mn, mx;
MinMax(l, r, &mn, &mx);
// cerr << mn << " " << mx << endl;
if(mx > mn) {
nums.pb(mn);
nums.pb(mx);
ll nl = mn + 1ll, nr = mx - 1ll;
ll nm = (nl + nr) >> 1ll;
solve_t2(nums, nl, nm, N);
solve_t2(nums, nm + 1ll, nr, N);
} else {
nums.pb(mn);
return;
}
}
void solve_t1(vll& nums, ll l, ll r, ll N) {
if(((ll)nums.size()) >= N) return;
if(r - l + 1ll <= 0ll) return;
ll mn, mx;
MinMax(l, r, &mn, &mx);
if(mn == -1ll) return;
if(mx > mn) {
nums.pb(mn);
nums.pb(mx);
solve_t1(nums, mn + 1ll, mx - 1ll, N);
} else {
nums.pb(mn);
return;
}
}
ll findGap(int T, int N)
{
vll ans;
if(T == 2) {
solve_t1(ans, 0ll, 1000000000000000000ll, N);
} else {
solve_t1(ans, 0ll, 1000000000000000000ll, N);
}
sort(ans.begin(), ans.end());
// for(int i = 0; i < N; i++) {
// cerr << ans[i] << " ";
// }
// cerr << endl;
ll maxgap = 0ll;
for(int i = 0; i < N - 1; i++) {
maxgap = max(maxgap, ans[i + 1] - ans[i]);
}
return maxgap;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |