Submission #436087

#	Time	Username	Problem	Language	Result	Execution time	Memory
436087		Lam_lai_cuoc_doi	Gap (APIO16_gap)	C++17	100 / 100	68 ms	2624 KiB

gap

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 1e6 + 5;

#include "gap.h"

long long findGap(int t, int n)
{
    if (t == 1)
    {
        vector<ll> a(n);
        ll l = 0, r = 1e18;

        for (int i = 0; i < (n + 1) / 2; ++i)
        {
            MinMax(l, r, &l, &r);
            a[i] = l;
            a[n - 1 - i] = r;
            ++l;
            --r;
        }

        ll ans(0);
        for (int i = 0; i < n - 1; ++i)
            ans = max(ans, a[i + 1] - a[i]);
        return ans;
    }
    else
    {
        ll l = 0, r = 1e18;
        MinMax(l, r, &l, &r);
        vector<ll> a;
        a.reserve(n);

        ll x = l, y = r, q = (r - l - 1) % (n - 1);

        for (int i = 1; i <= n - 1; ++i)
        {
            ll v = (y - x - 1) / (n - 1) + (q > 0);
            --q;

            ++l;
            r = l + v - 1;
            ll e, f;

            MinMax(l, r, &e, &f);

            l = r;

            if (e != -1)
            {
                a.emplace_back(e);
                a.emplace_back(f);
            }
        }

        a.emplace_back(x);
        a.emplace_back(y);

        sort(a.begin(), a.end());

        ll ans(0);
        for (int i = 0; i < (int)a.size() - 1; ++i)
            ans = max(ans, a[i + 1] - a[i]);
        return ans;
    }
}

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