| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 101883 | KCSC | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#ifndef HOME
#include "gap.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef HOME
const int DIM = 100005;
long long arr[DIM]; int N;
void MinMax(long long a, long long b, long long &mn, long long &mx) {
mn = 1LL << 60, mx = -1LL << 60;
for (int i = 1; i <= N; ++i) {
if (arr[i] >= a and arr[i] <= b) {
mn = min(mn, arr[i]); mx = max(mx, arr[i]); } }
if (mn > mx) {
mn = mx = -1; } }
#endif
long long findGap(int t, int n) {
long long mn, mx, ans = 0;
MinMax(0, 1LL << 60, mn, mx);
if (t == 1) {
for (int i = 1; i < (n + 1) / 2; ++i) {
long long mn2, mx2;
MinMax(mn + 1, mx - 1, mn2, mx2);
ans = max(ans, mn2 - mn); ans = max(ans, mx - mx2);
mn = mn2; mx = mx2; }
ans = max(ans, mx - mn); }
else {
long long sz = (mx - mn + n - 1) / n, ls = mn;
for (long long st = mn + 1, en = mn + sz, i = 1; i <= n; st += sz, en += sz, ++i) {
if (en > mx - 1) { en = mx - 1; }
if (st > en) { break; }
long long mn2, mx2;
MinMax(st, en, mn2, mx2);
if (mn2 != -1) {
ans = max(ans, mn2 - ls); ls = mx2; } }
ans = max(ans, mx - ls); }
return ans; }
#ifdef HOME
int main(void) {
freopen("gap.in", "r", stdin);
freopen("gap.out", "w", stdout);
int n; cin >> n; N = n;
for (int i = 1; i <= n; ++i) {
cin >> arr[i]; }
sort(arr + 1, arr + n + 1);
cout << findGap(1, n) << " " << findGap(2, n) << endl;
return 0; }
#endif