Submission #535574

#	Time	Username	Problem	Language	Result	Execution time	Memory
535574		daisy	Gap (APIO16_gap)	C++17	30 / 100	65 ms	1188 KiB

gap

#include<iostream>
#include "gap.h"
#define l 1000000000000000000
using namespace std;
long long subt1(long long n)
{
    long long tf,ts,pf,ps,mr=0;

    MinMax(0,l,&tf,&ts);

    for(int i=2;i<=n/2;i++)
    {
        pf=tf;ps=ts;
        MinMax(pf+1,ps-1,&tf,&ts);

        if(tf-pf>mr) mr=tf-pf;
        if(ps-ts>mr) mr=ps-ts;
    }
    if(n%2)
    {
        if(tf+1<=ts-1)
        MinMax(tf+1,ts-1,&pf,&ps);
        if(pf-tf>mr) mr=pf-tf;
        if(ts-pf>mr) mr=ts-pf;
    }
    else if(ts-tf>mr) mr=ts-tf;
    return mr;
}
long long subt2(long long n)
{
    long long tl,tr,le,ri,mi,ma,pma=0,mr=0;
    MinMax(0,l,&tl,&tr);

    long long in=(tr-tl+1)/(n-1);
    le=tl+1;ri=le+in;

    for(int i=1;i<n;i++)
    {
        MinMax(le,ri,&mi,&ma);
        le+=in;ri+=in;
        if(mr<mi-pma)
          mr=mi-pma;
        if(ma!=-1) pma=ma;
    }
    if(le<=tr)
    {
        MinMax(le,tr,&mi,&ma);
        if(mi==-1)
        {
            mr=max(mr,tr+1-pma);
        }
        else
        {
            mr=max(mr,mi-pma);
            mr=max(mr,tr+1-ma);
        }
    }
    return mr;
}
long long findGap(int T, int N)
{
    if(T==1)
    return subt1(N);
	else return subt2(N);
}

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