Submission #712711

#	Time	Username	Problem	Language	Result	Execution time	Memory
712711		onepunchac168	Gap (APIO16_gap)	C++14	30 / 100	66 ms	1860 KiB

gap

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

using namespace std;
long long a[100005];
#define ll long long
long long findGap(int t, int n)
{
    if (t==1){
        long long gmin=0;
        long long gmax=1e18;
        for (int i=1;i<=n/2;i++)
        {
            long long aa,bb;
            MinMax(gmin,gmax,&aa,&bb);
            a[i]=aa;
            a[n-i+1]=bb;
            gmin=aa+1;
            gmax=bb-1;
        }
        if (n%2==1)
        {
            long long aa,bb;
            MinMax(gmin,gmax,&aa,&bb);
            gmin=aa;
            gmax=bb;
            a[n/2+1]=gmin;
        }
        long long  res=0;
        for (int i=2;i<=n;i++)
        {
            res=max(res,a[i]-a[i-1]);
        }
        return res;
    }
    else
    {
        long long aa,bb;
        long long gmin=0;
        long long gmax=1e18;
        MinMax(gmin,gmax,&aa,&bb);
        gmin=aa;
        gmax=bb;
        ll pp=(bb-aa+1)/(n-1);
        ll res=0;
        ll before=-1;
        for (int i=1;i<=n-1;i++)
        {
            if (i==n-1)
            {
                gmin=gmax+1;
                gmax=bb;
            }
            else if (i==1)
            {
                gmin=aa;
                gmax=aa+pp-1;
            }
            else
            {
                gmin=gmax+1;
                gmax=gmin+pp-1;
            }
            long long cc,dd;
            MinMax(gmin,gmax,&cc,&dd);
            if (cc==-1&&dd==-1)
            {
                continue;
            }
            else
            {
                if (cc!=dd)
                {
                    if (before!=-1)
                    {
                        res=max(res,cc-before);
                    }
                    before=dd;
                    continue;
                }
                else
                {
                    if (before!=-1)
                    {
                        res=max(res,cc-before);
                    }
                    before=dd;
                }
            }
        }
        return res;
    }
}

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