제출 #48388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48388		BThero	Gap (APIO16_gap)	C++17	100 / 100	75 ms	2940 KiB

gap

// Why am I so stupid? :c
#include <bits/stdc++.h>
#include "gap.h"

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

typedef long long ll;

using namespace std;

long long findGap(int t, int n) {
    ll arr[n * 2 + 5], que[2], ret = 0;
    int sz = 0;

    if (n <= 5 || t == 1) {
        arr[0] = 0, arr[n + 1] = (ll)1e18 + 1;
        int l = 1, r = n;

        while (l <= r) {
            MinMax(arr[l - 1] + 1, arr[r + 1] - 1, arr + l, arr + r);
            ++l, --r;
        }

        for (int i = 1; i < n; ++i) {
            ret = max(ret, arr[i + 1] - arr[i]);
        }
    }
    else {
        MinMax(1, (ll)1e18, que, que + 1);
        ll l = que[0], r = que[1];

        arr[++sz] = l++;
        arr[++sz] = r--;

        ll a = (r - l + 1) / (n - 1);
        ll b = (r - l + 1) % (n - 1);
        ll cur = l;

        for (int i = 1; i < n; ++i) {
            ll len = a;

            if (b > 0) {
                ++len, --b;
            }

            MinMax(cur, cur + len - 1, que, que + 1);

            if (que[0] != -1) {
                arr[++sz] = que[0];
                arr[++sz] = que[1];
            }

            cur += len;
        }

        sort(arr + 1, arr + sz + 1);
        sz = unique(arr + 1, arr + sz + 1) - arr - 1;

        for (int i = 1; i < sz; ++i) {
            ret = max(ret, arr[i + 1] - arr[i]);
        }
    }

    return ret;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70