Submission #733920

#	Time	Username	Problem	Language	Result	Execution time	Memory
733920		turbat	Gap (APIO16_gap)	C++14	48.54 / 100	57 ms	1208 KiB

gap

#include "gap.h"

#include <iostream>
using namespace std;

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

    MinMax(-1, 1e18 + 1, &mn, &mx);
    long long gap = (mx - mn) / (N - 1);
    // cout << gap << endl;
    for (long long 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 - gap + 1 <= 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;
            gap = l - cur;
            // cout << gap << endl;
        }
        cur = r;
    }

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

    return gap;
}

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