Submission #945364

#	Time	Username	Problem	Language	Result	Execution time	Memory
945364		wii	Gap (APIO16_gap)	C++17	100 / 100	42 ms	4000 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll findGap(int T, int N) {
    ll res = 0;
    if (T == 1) {
        vector<ll> a;
        for (ll l = 0, r = 1e18; l <= r && a.size() < N; ) {
            ll mn, mx;
            MinMax(l, r, &mn, &mx);

            a.push_back(mn);
            a.push_back(mx);

            l = mn + 1;
            r = mx - 1;
        }

        sort(a.begin(), a.end());
        for (int i = 1; i < a.size(); ++i)
            res = max(res, a[i] - a[i - 1]);
    } else {
        ll l, r;
        MinMax(0, 1e18, &l, &r);

        ll step = (r - l + 1) / N;

        res = step;
        for (ll i = l + 1, pre = l; i <= r; i += step + 1) {
            ll mn, mx;
            MinMax(i, i + step, &mn, &mx);

            if (mn != -1) {
                res = max(res, mn - pre);
                pre = mx;
            }
        }
    }

	return res;
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:11:53: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |         for (ll l = 0, r = 1e18; l <= r && a.size() < N; ) {
      |                                            ~~~~~~~~~^~~
gap.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int i = 1; i < a.size(); ++i)
      |                         ~~^~~~~~~~~~

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