Submission #733904

#	Time	Username	Problem	Language	Result	Execution time	Memory
733904		turbat	Gap (APIO16_gap)	C++14	0 / 100	3090 ms	1104 KiB

gap

#include "gap.h"

#include <iostream>
using namespace std;

long long findGap(int T, int N) {
    long long mn, mx;

    MinMax(0, 1e18, &mn, &mx);
    long long gap = (mx - mn) / (N - 1);
    for (int cur = mn; cur < mx;) {
        long long l, r;
        // cout << cur << " " << cur + gap << " ";
        MinMax(cur, cur + gap, &l, &r);
        // cout << l << " " << r << endl;

        if (l == r) {
            long long tmp = gap;
            l = -1;
            while (l == -1 && cur + tmp <= mx) {
                tmp += gap;
                // cout << "WHILE: " << cur + tmp - gap + 1 << " " << cur + tmp
                // << " ";
                MinMax(cur + tmp - gap + 1, cur + tmp, &l, &r);
                // cout << l << " " << r << endl;
            }
            // cout << l << " " << cur << endl;
            if (gap > l - cur) return gap;
            gap = l - cur;
            cur = l;
        } else {
            cur = r;
        }
    }

    // cout << "GAP: " << gap << endl;

    return gap;
}

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