Submission #947253

#	Time	Username	Problem	Language	Result	Execution time	Memory
947253		NValchanov	Gap (APIO16_gap)	C++17	57.64 / 100	43 ms	4240 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) / n;

    ll ans = cnt;
    ll last = minel;

    ll cur = minel + 1;

    while(cur <= maxel)
    {
        ll cur_minel;
        ll cur_maxel;
        MinMax(cur, cur + cnt, &cur_minel, &cur_maxel);

        if(cur_minel != -1)
        {
            ans = max(ans, cur_minel - last);
            last = cur_maxel;
        }

        cur += cnt;
    }

    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: 57.6396140649 / 70