Submission #813115

#	Time	Username	Problem	Language	Result	Execution time	Memory
813115		Pikachu	Gap (APIO16_gap)	C++17	100 / 100	46 ms	1864 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;

int solve2()
{
    MinMax(0, oo, tmpn, tmpx);
    a[++cnt] = *tmpn;
    a[++cnt] = *tmpx;
    int step = (*tmpx - *tmpn + n) / (n - 1);
    for (int i = 1, cur = *tmpn; i < n; i++) {
        // cout << i << endl;
        MinMax(cur + 1, cur + step, tmpn, tmpx);
        cur += step;
        if (*tmpn == -1) continue;
        a[++cnt] = *tmpn;
        if (*tmpn != *tmpx) a[++cnt] = *tmpx;
    }
    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: 70 / 70