Submission #567641

#	Time	Username	Problem	Language	Result	Execution time	Memory
567641		four_specks	Gap (APIO16_gap)	C++17	70 / 100	55 ms	1872 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

using namespace std;

long long findGap(int T, int N)
{
    if (T == 1)
    {
        vector<long long> a(N);
        long long mn = 0, mx = LLONG_MAX;
        for (int l = 0, r = N - 1; l < r; l++, r--)
        {
            MinMax(mn, mx, &mn, &mx);
            if (mn != -1)
            {
                a[l] = mn, a[r] = mx;
                mn += 1, mx -= 1;
            }
            else
                assert(0);
        }

        long long gap = 0;
        for (int i = 0; i < N - 1; i++)
            gap = max(gap, a[i + 1] - a[i]);

        return gap;
    }
    else if (T == 2)
    {
        long long l = 0, r = LLONG_MAX;
        MinMax(l, r, &l, &r);

        long long block = (r - l + 1) / (N - 1);

        long long gap = 0;

        long long x = l;
        for (l += 1; l <= r; l += block + 1)
        {
            long long mn, mx;
            MinMax(l, l + block, &mn, &mx);
            if (mn != -1)
            {
                gap = max(gap, mn - x);
                x = mx;
            }
        }

        return gap;
    }
    else
        assert(0);

    return 0;
}

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