Submission #272674

#	Time	Username	Problem	Language	Result	Execution time	Memory
272674		toonewbie	Gap (APIO16_gap)	C++17	100 / 100	79 ms	2040 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long

ll A[100005];
ll findGap(int T, int N) {
    if (T == 1) {
        ll a = 0, b = 1e18;
        int l = 0, r = N - 1;
        while(l <= r) {
            MinMax(a, b, &a, &b);
            A[l++] = a++; A[r--] = b--;
        }
        a = 0;
        for (int i = 1; i < N; i++) a = max(a, A[i] - A[i - 1]);
        return a;
    } else {
        ll a, b, res = 0;
        MinMax(0, 1e18, &a, &b);
        if (b - a + 1 == N) return 1;
        ll sz = (b - (a + 1)) / (N - 1);
        /// [a + 1, a + sz + 1], [a + sz + 2, a + ]
        ll last = a, X, Y;
        for (ll x = a + 1; x <= b - 1; x += sz + 1) {
            /// [x, x + sz]
            MinMax(x, x + sz, &X, &Y);
            if (X != -1) res = max(res, X - last);
            if (Y != -1) last = Y;
        }
        return max(res, b - last);
    }
	return 0;
}

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