Submission #78113

#	Time	Username	Problem	Language	Result	Execution time	Memory
78113		aquablitz11	Gap (APIO16_gap)	C++14	100 / 100	84 ms	39848 KiB

gap

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

using ll = long long;
const int N = 1e5+10;
ll A[N];

long long findGap(int t, int n)
{
    if (t == 1) {
        ll mn = 0, mx = 1e18;
        for (int i = 1; i <= (n+1)/2; ++i) {
            MinMax(mn, mx, &mn, &mx);
            A[i] = mn++;
            A[n-i+1] = mx--;
        }
        ll ans = 0;
        for (int i = 2; i <= n; ++i)
            ans = max(ans, A[i]-A[i-1]);
        return ans;
    } else {
        ll mn, mx;
        MinMax(0, 1e18, &mn, &mx);
        ll z = n-2 == 0 ? 0 : (mx-mn-1)/(n-2);
        vector<ll> num;
        num.push_back(mn);
        for (int i = 0; i < n-2; ++i) {
            ll l = mn+1 + z*i;
            ll r = mn+1 + z*(i+1) - 1;
            if (i == n-3) r = mx-1;
            ll mn2, mx2;
            MinMax(l, r, &mn2, &mx2);
            if (mn2 != -1) {
                num.push_back(mn2);
                num.push_back(mx2);
            }
        }
        num.push_back(mx);
        ll ans = 0;
        for (int i = 1; i < num.size(); ++i)
            ans = max(ans, num[i]-num[i-1]);
        return ans;
    }
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:41:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < num.size(); ++i)
                         ~~^~~~~~~~~~~~

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