Submission #272666

#	Time	Username	Problem	Language	Result	Execution time	Memory
272666		toonewbie	Gap (APIO16_gap)	C++17	0 / 100	75 ms	1944 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 = -1, b = 1e18 + 1;
        int l = 0, r = N - 1;
        while(l <= r) {
            MinMax(a + 1, b - 1, &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);
            res = max(res, X - last);
            last = Y;
        }
        return max(res, b - last);
    }
	return 0;
}

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