Submission #218203

#	Time	Username	Problem	Language	Result	Execution time	Memory
218203		SamAnd	Gap (APIO16_gap)	C++17	100 / 100	82 ms	4148 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 100005;
const long long M = 1000000000000000000;

int n;
long long a[N];

int h[N];

long long findGap(int T, int N)
{
    n = N;
    if (T == 1)
    {
        a[0] = -1;
        a[n + 1] = M + 1;
        for (int l = 1, r = n; l <= r; ++l, --r)
        {
            long long minu, maxu;
            MinMax(a[l - 1] + 1, a[r + 1] - 1, &minu, &maxu);
            a[l] = minu;
            a[r] = maxu;
        }
        long long ans = 0;
        for (int i = 1; i < n; ++i)
            ans = max(ans, a[i + 1] - a[i]);
        return ans;
    }
    long long minu, maxu;
    MinMax(0, M, &minu, &maxu);
    if (n == 2)
        return maxu - minu;
    long long d = maxu - minu - 1;
    vector<long long> v;
    for (int i = 0; i < n - 2; ++i)
        v.push_back(d / (n - 2));
    for (int i = 0; i < d % (n - 2); ++i)
        ++v[i];
    vector<pair<long long, long long> > vv;
    vv.push_back(m_p(minu, minu));
    long long u = minu;
    for (int i = 0; i < v.size(); ++i)
    {
        long long l = u + 1;
        long long r = l + v[i] - 1;
        long long minu, maxu;
        MinMax(l, r, &minu, &maxu);
        vv.push_back(m_p(minu, maxu));
        u = r;
    }
    vv.push_back(m_p(maxu, maxu));
    for (int i = n - 2; i >= 0; --i)
    {
        if (vv[i + 1].first != -1)
            h[i] = i + 1;
        else
            h[i] = h[i + 1];
    }
    long long ans = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        if (vv[i].first == -1)
            continue;
        ans = max(ans, vv[h[i]].first - vv[i].second);
    }
    return ans;
}

Compilation message (stderr)

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

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