Submission #709289

#	Time	Username	Problem	Language	Result	Execution time	Memory
709289		lmqzzz	Gap (APIO16_gap)	C++14	100 / 100	53 ms	2876 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>
using namespace std;
#define int64_t long long

long long findGap(int T, int N) {
        if (T == 1) {
                vector<int64_t> l, r;
                int times = N + 1 >> 1;
                int64_t ll = 0, rr = 1e18;
                while (times--) {
                        int64_t a, b;
                        MinMax(ll, rr, &a, &b);
                        l.emplace_back(a);
                        r.emplace_back(b);
                        ll = a + 1, rr = b - 1;
                }
                if (l.back() == r.back()) l.pop_back();
                reverse(r.begin(), r.end());
                l.insert(l.end(), r.begin(), r.end());
                int64_t res = 0;
                for (int i = 1; i < N; i++) res = max(res, l[i] - l[i - 1]);
                return res;
        } else {
                int64_t res = 0;
                int64_t LIMIT_LEFT, LIMIT_RIGHT;
                MinMax(0, 1e18, &LIMIT_LEFT, &LIMIT_RIGHT);
                if (N == 2) return LIMIT_RIGHT - LIMIT_LEFT;
                LIMIT_LEFT++;
                LIMIT_RIGHT--;
                N -= 2;
                const int64_t BLOCK_SIZE = (LIMIT_RIGHT - LIMIT_LEFT + N) / (N + 1);
                int64_t cur_l = LIMIT_LEFT;
                int64_t last = LIMIT_LEFT - 1;
                while (cur_l <= LIMIT_RIGHT) {
                        int64_t l = cur_l;
                        int64_t r = cur_l + BLOCK_SIZE - 1;
                        r = min<int64_t>(r, LIMIT_RIGHT);
                        cur_l = r + 1;
                        int64_t a, b;
                        MinMax(l, r, &a, &b);
                        if (a == -1) continue;
                        if (last != -1) res = max(res, a - last);
                        last = b;
                }
                res = max(res, LIMIT_RIGHT + 1 - last);
                return res;
        }
        return 0;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:10:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |                 int times = N + 1 >> 1;
      |                             ~~^~~

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