Submission #733871

#	Time	Username	Problem	Language	Result	Execution time	Memory
733871		turbat	Gap (APIO16_gap)	C++14	0 / 100	3097 ms	1172 KiB

gap

#include "gap.h"

#include <iostream>
using namespace std;

long long findGap(int T, int N) {
    // cout << "T: " << T << " N: " << N << endl;
    long long mn, mx;

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

        if (l == r) {
            // time to binary search hhe
            long long tmp = gap;
            while (cur != l && cur + tmp <= mx) {
                tmp += gap;
                // cout << cur + tmp - gap + 1 << " " << cur + tmp << " ";
                MinMax(cur + tmp - gap + 1, cur + tmp, &l, &r);
                // cout << l << " " << r << endl;
                // cout << cur + tmp - gap + 1 << " " << cur + tmp << " " << l
                // << " " << r << endl;
            }
            gap = l - cur;
            cur = l;
        } else {
            cur = r;
        }
    }

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

    return gap;
}

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