Submission #222269

#	Time	Username	Problem	Language	Result	Execution time	Memory
222269		Bruteforceman	Gap (APIO16_gap)	C++11	70 / 100	66 ms	3312 KiB

gap

#include "bits/stdc++.h"
#include "gap.h"
using namespace std;
const long long maxV = 1e18;

long long findGap(int T, int N)
{
    long long mx, mn;
    MinMax(0, maxV, &mn, &mx);
    long long lower = (mx - mn + N - 2) / (N - 1);
    long long cur = mn + 1;
    vector <long long> v ({mn});
    int cnt = N - 1; 
    while(cur <= mx) {
        long long p, q;
        MinMax(cur, min(mx, cur + lower), &p, &q);    
        cur += lower + 1;
        if(p != -1) {
            if(!v.empty()) {
                lower = max(lower, p - v.back());
            }
            v.push_back(p);
            v.push_back(q);
            cnt -= (p == q) ? 1 : 2;
        } else {
            lower = max(lower, min(mx, cur) - v.back());
        }
        if(cnt) lower = max(lower, (mx - v.back() + cnt - 1) / cnt);
        // cout << cur << " " << min(mx, cur + lower - 1) << " " << p << " " << q << endl;
    }
	return lower;
}

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