Submission #1149716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149716		vladilius	Gap (APIO16_gap)	C++20	12.88 / 100	149 ms	5920 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;

ll findGap(int T, int n){
    ll l, r;
    
    MinMax(0, inf, &l, &r);
    set<ll> f;
    f.insert(l);
    f.insert(r);
    
    ll bl = (r - l) / n, br = (r - l);
    
    auto check = [&](ll m){
        if (m == 1) return 1;
        ll k = *f.begin();
        while (k != *prev(f.end())){
            auto it = f.upper_bound(k);
            if (it != f.end() && (*it) <= (k + m - 1)){
                k = *it;
                continue;
            }
            MinMax(k + 1, k + m - 1, &l, &r);
            if (l == -1) return 1;
            f.insert(l);
            f.insert(r);
            k = r;
        }
        return 0;
    };
    
    while (bl + 1 < br){
        ll m = (bl + br) / 2;
        if (check(m)){
            bl = m;
        }
        else {
            br = m - 1;
        }
    }
    if (check(br)) bl = br;
    
    return bl;
}

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