Submission #733923

#	Time	Username	Problem	Language	Result	Execution time	Memory
733923		turbat	Gap (APIO16_gap)	C++14	78.54 / 100	52 ms	1876 KiB

gap

#include "gap.h"

#include <algorithm>
#include <iostream>
using namespace std;

long long Subtask1(int T, int N) {
    long long mn = 0, mx = 0, r = N, l = 1, a[N + 1], right = 1e18, left = 0,
              k = 0;
    while (r >= l) {
        MinMax(left, right, &left, &right);
        a[l] = left;
        a[r] = right;
        left++;
        right--;
        l++;
        r--;
    }
    long long ans = 0;
    for (int i = 1; i < N; i++) ans = max(ans, a[i + 1] - a[i]);
    return ans;
}

long long findGap(int T, int N) {
    if (T == 1) {
        return Subtask1(T, 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;
}

Compilation message (stderr)

gap.cpp: In function 'long long int Subtask1(int, int)':
gap.cpp:8:15: warning: unused variable 'mn' [-Wunused-variable]
    8 |     long long mn = 0, mx = 0, r = N, l = 1, a[N + 1], right = 1e18, left = 0,
      |               ^~
gap.cpp:8:23: warning: unused variable 'mx' [-Wunused-variable]
    8 |     long long mn = 0, mx = 0, r = N, l = 1, a[N + 1], right = 1e18, left = 0,
      |                       ^~
gap.cpp:9:15: warning: unused variable 'k' [-Wunused-variable]
    9 |               k = 0;
      |               ^

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