Submission #813084

#	Time	Username	Problem	Language	Result	Execution time	Memory
813084		Pikachu	Gap (APIO16_gap)	C++17	43.49 / 100	52 ms	1888 KiB

gap

#include <bits/stdc++.h>
#define int long long

using namespace std;

template<typename T>
inline bool maxi(T &x, const T &val)
{
    if (x < val) return x = val, true;
    return false;
}

template<typename T>
inline bool mini(T &x, const T &val)
{
    if (x > val) return x = val, true;
    return false;
}

const int maxn = 3e5 + 10, oo = 1e18;
int n;
int a[maxn];
int res;

void MinMax(long long s, long long t, long long *mn, long long *mx);

int solve1()
{
    int st = 0, en = oo;
    int *tmpn = new int(0), *tmpx = new int(oo);
    int curst = 1, curen = n;
    while (curst <= curen) {
        MinMax(st, en, tmpn, tmpx);
        a[curst++] = *tmpn;
        st = *tmpn + 1;
        a[curen--] = *tmpx;
        en = *tmpx - 1;
    }
    for (int i = 1; i < n; i++) {
        maxi(res, a[i + 1] - a[i]);
    }
    return res;
}

int *tmpn = new int(0), *tmpx = new int(0);
int cnt = 0;

void DAC(int l, int r)
{
    if (l > r) return;
    if (cnt == n) return;
    MinMax(l, r, tmpn, tmpx);
    if (*tmpn == -1) return;
    a[++cnt] = *tmpn;
    if (*tmpn == *tmpx) return;
    a[++cnt] = *tmpx;
    l = *tmpn + 1;
    r = *tmpx - 1;
    if (r - l <= (a[2] - a[1]) / max(1ll, (n - 2))) {
        while (l <= r) {
            MinMax(l, r, tmpn, tmpx);
            if (*tmpn == -1) return;
            a[++cnt] = *tmpn;
            if (*tmpn == *tmpx) break;
            a[++cnt] = *tmpx;
            l = *tmpn + 1;
            r = *tmpx - 1;
        }
        return;
    }
    int mid1 = (l * 2 + r) / 3;
    int mid2 = (l + r * 2) / 3;
    DAC(l, mid1);
    DAC(mid1 + 1, mid2);
    DAC(mid2 + 1, r);
}

int solve2()
{
    DAC(0, oo);
    sort(a + 1, a + cnt + 1);
    for (int i = 1; i < cnt; i++) {
        maxi(res, a[i + 1] - a[i]);
    }
    return res;
}

int findGap(signed sub, signed n)
{
    ::n = n;
    if (sub == 1) return solve1();
    else return solve2();
}

#undef int

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