Submission #947259

#	Time	Username	Problem	Language	Result	Execution time	Memory
947259		NValchanov	Gap (APIO16_gap)	C++17	100 / 100	45 ms	4188 KiB

gap

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

#define endl '\n'

using namespace std;

typedef long long ll;

const ll INF = 4e18;

ll t,n;

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

    while(left <= right && a.size() < n)
    {
        MinMax(left, right, &minel, &maxel);

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

        left = minel + 1;
        right = maxel - 1;
    }
    sort(a.begin(), a.end());
    ll ans = 0;
    for(int i = 1; i < a.size(); 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 + 1);
    }

    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);
}

Compilation message (stderr)

gap.cpp: In function 'll solve_t1()':
gap.cpp:23:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   23 |     while(left <= right && a.size() < n)
      |                            ~~~~~~~~~^~~
gap.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 1; i < a.size(); i++)
      |                    ~~^~~~~~~~~~
gap.cpp:21:8: warning: unused variable 'cnt' [-Wunused-variable]
   21 |     ll cnt = 0;
      |        ^~~

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