This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#define f first
#define s second
#define ll long long
#define ii pair<ll, ll>
ii get(ll a, ll b) {
b = min(b, (ll)1e18);
ii x;
MinMax(a, b, &x.f, &x.s);
return x;
}
long long findGap(int T, int N)
{
if (T == 1) {
vector<ll> nums, nums2;
ii range = make_pair(1, (ll)1e18);
for (int i = 0; i < (N+1)/2; i++) {
if (range.f > range.s) break;
ii res = get(range.f, range.s);
if (res.f == -1) break;
nums.push_back(res.f); nums2.push_back(res.s);
range = make_pair(res.f+1, res.s-1);
}
reverse(nums2.begin(), nums2.end());
for (int x : nums2) nums.push_back(x);
ll best = 0;
for (int i = 0; i < nums.size() - 1; i++) {
best = max(best, nums[i+1] - nums[i]);
}
return best;
}
ii boundary = get(1, 1e18);
ll block = (boundary.s-boundary.f)/(N-1);
ll prev = boundary.f;
ll ans = 0;
for (ll cur = boundary.f + 1; cur < boundary.s; cur += block) {
ii thing = get(cur, cur+block);
if (thing.f == -1) continue;
ans = max(ans, thing.f - prev);
prev = thing.s;
}
ans = max(ans, boundary.s - prev);
return ans;
}
Compilation message (stderr)
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = 0; i < nums.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |