Submission #947248

#	Time	Username	Problem	Language	Result	Execution time	Memory
947248		NValchanov	Gap (APIO16_gap)	C++17	0 / 100	3100 ms	4096 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

#define endl '\n'

using namespace std;

typedef long long ll;

const ll INF = 1e18;

ll t,n;

ll solve_t1()
{
    vector <ll> a;
    ll left = 0;
    ll right = INF;
    ll minel;
    ll maxel;
    ll cnt = 0;

    while(left <= right && 2 * cnt < n)
    {
        MinMax(left, right, &minel, &maxel);

        a.push_back(minel);
        a.push_back(maxel);

        cnt++;

        left = minel + 1;
        right = maxel - 1;
    }
    sort(a.begin(), a.end());
    ll ans = 0;
    for(int i = 1; i < n; i++)
    {
        ans = max(ans, a[i] - a[i - 1]);
    }
    return ans;
}

ll solve_t2()
{
    ll minel;
    ll maxel;

    MinMax(0, INF, &minel, &maxel);

    ll cnt = (maxel - minel + 1) / 2;

    ll ans = 0;
    ll last = minel;

    for(int i = minel; i <= maxel; i += cnt)
    {
        MinMax(i, i + cnt, &minel, &maxel);

        if(minel == -1)
        {
            ans = max(ans, minel - last);
            last = maxel;
        }
    }
    return ans;
}

ll findGap(int T, int N)
{
    t = T;
    n = N;
    if(t == 1)
        return solve_t1();
    else if(t == 2)
        return solve_t2();
    else
        assert(false);
}

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