Submission #1207403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207403		jasonic	Gap (APIO16_gap)	C++20	100 / 100	39 ms	3008 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
const ll MINN = 0;
const ll MAXN = 1e18;

ll solve1(int N) {
    ll mn = MINN, mx = MAXN;
    queue<ll> left;
    stack<ll> right;

    while(true) {
        ll l, r;
        MinMax(mn, mx, &l, &r);
        if(l == r) {
            left.push(l);
        } else {
            left.push(l);
            right.push(r);
        }
        
        mn = l + 1;
        mx = r - 1;

        if(left.size() + right.size() == N) break;
    }

    vector<ll> a;
    while(!left.empty()) {
        a.push_back(left.front());
        left.pop();
    }

    while(!right.empty()) {
        a.push_back(right.top());
        right.pop();
    }

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

ll solve2(int N) {
    ll rangeL, rangeR;
    MinMax(0, MAXN, &rangeL, &rangeR);
    ll step = ( (rangeR - rangeL - 1) + N - 1) / (N - 1);
    ll ans = step, x, y, l = rangeL, i;
    for(i = rangeL; i < rangeR; i += step + 1) {
        MinMax(i, min(i + step, rangeR), &x, &y);
        if(x != -1) {
            ans = max(ans, x - l);
            l = y;
        }
    }
    return ans;
}

ll findGap(int T, int N) {
    if(T == 1) {
        return solve1(N);
    } else if(T == 2) {
        return solve2(N);
    }
    return 42;
}

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