Submission #556896

#	Time	Username	Problem	Language	Result	Execution time	Memory
556896		Sharky	Gap (APIO16_gap)	C++17	100 / 100	66 ms	2256 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std; 
#define pb push_back
const long long inf = 1e18;
long long findGap(int T, int N) {
    if (T == 1) {
        pair<long long, long long> range = {1, inf};
        long long cnt = 0, mn, mx; 
        vector<long long> a; 
        for (long long i = 0; i < (N + 1) / 2; i++) {
            MinMax(range.first, range.second, &mn, &mx);
            range = {mn + 1, mx - 1};
            a.pb(mn); a.pb(mx);
        }
        sort(a.begin(), a.begin() + N); 
        long long ans = 0;
        for (long long i = 1; i < N; i++) ans = max(ans, a[i] - a[i - 1]);
        return ans; 
    }
    long long L = 1, R = inf, mn, mx; 
    MinMax(L, R, &mn, &mx);
    long long hole = (mx - mn - 1 + (N - 1)) / (N - 1);
    long long MN, MX, i, ans = hole, lst = mn;
    for (i = mn; i + hole < mx; i += hole + 1) {
        MinMax(i, i + hole, &MN, &MX);
        if (MN != -1) ans = max(ans, MN - lst), lst = MX; 
    }
    MinMax(i, mx, &MN, &MX);
    if (MN != -1) ans = max(ans, MN - lst);
    return ans; 
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:9:19: warning: unused variable 'cnt' [-Wunused-variable]
    9 |         long long cnt = 0, mn, mx;
      |                   ^~~

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