Submission #733933

#	Time	Username	Problem	Language	Result	Execution time	Memory
733933		turbat	Gap (APIO16_gap)	C++14	30 / 100	44 ms	1864 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, l, r;

    MinMax(-1, 1e18 + 1, &mn, &mx);
    long long gap = (mx - mn) / (N - 1), last = mn;
    for (long long cur = mn + 1; cur < mx;) {
        l = -1;
        long long tmp = gap;
        while (l == -1 && cur + tmp - gap <= mx) {
            tmp += gap;
            // cout << cur + tmp - gap << " " << cur + tmp << endl;
            MinMax(cur + tmp - gap, cur + tmp, &l, &r);
        }
        if (l == -1) return gap;
        gap = l - cur;

        last = r;
        cur = r + 1;
    }
    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;
      |               ^
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:31:42: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   31 |     long long gap = (mx - mn) / (N - 1), last = mn;
      |                                          ^~~~

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