Submission #1198685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198685		nvc2k8	Gap (APIO16_gap)	C++20	100 / 100	39 ms	1964 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
#define TASK "gap"
#define INT_LIM (int) 2147483647
#define LL_LIM (long long) 9223372036854775807
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define ll long long
#define pii pair<int,int>
using namespace std;
///------------------------------------------///

ll a[100005];

long long findGap(int T, int N)
{
    if (T==1)
    {
        ll mn = 0, mx = 1e18;
        FOR(i, 1, (N+1)/2)
        {
            ll newmin, newmax;
            MinMax(mn, mx, &newmin, &newmax);

            a[i] = newmin;
            a[N-i+1] = newmax;
            mn = newmin+1;
            mx = newmax-1;
        }

        ll ret = 0;
        FOR(i, 1, N-1)
        {
            ret = max(ret, a[i+1]-a[i]);
        }
        return ret;
    }

    ll n = N;
    MinMax(0, 1e18, &a[1], &a[n]);
    ll v = (a[n]-a[1]+(n-1)-1)/(n-1);

    ll ret = 0, lastv = a[1];

    for (ll l = a[1]+1; l<a[n]; l+=v)
    {
        ll r = l+v-1;
        r = min(r, a[n]-1);
        ll minr = -1, maxr = -1;
        MinMax(l, r, &minr, &maxr);
        if (minr!=-1)
        {
            ret = max(ret, minr-lastv);
        }
        if (maxr!=-1) lastv = maxr;
    }
    ret = max(ret, a[n]-lastv);


    return ret;
}


//signed main()
//{
//    ///--------------------------///
//    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    if (fopen(TASK".INP","r")!=NULL)
//    {
//        freopen(TASK".INP","r",stdin);
//        freopen(TASK".OUT","w",stdout);
//    }
//    ///--------------------------///
//
//    return 0;
//}
//
/////------------------------------------------///

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