| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1352908 | bozho | Gap (APIO16_gap) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "gap.h"
#define endl '\n'
using namespace std;
const int MAX = (2e5) + 5;
long long a[MAX];
long long findGap(int t, int n)
{
if (t == 1)
{
long long l = 0, r = (1e18) + 1, s, t;
for (int i = 1; i <= (n + 1) / 2; i++)
{
MinMax(l, r, &s, &t);
a[i] = s;
a[n - i + 1] = t;
l = s + 1;
r = t - 1;
}
long long ans = 0;
for (int i = 2; i <= n; i++)
ans = max(ans, a[i] - a[i - 1]);
return ans;
}
long long l = 0, r = (1e18) + 1, lr = -1, s, t;
MinMax(l, r, &s, &t);
long long x = (t - s + n - 2) / (n - 1);
long long ans = x;
for (long long i = s; i < t; i += x + 1)
{
if (i + x >= t)
MinMax(i, t, &l, &r);
else
MinMax(i, i + x, &l, &r);
if (l != -1 && lr != -1)
ans = max(ans, l - lr);
lr = r;
}
return ans;
}