Submission #646356

#	Time	Username	Problem	Language	Result	Execution time	Memory
646356		Tenis0206	Gap (APIO16_gap)	C++11	14.14 / 100	159 ms	1104 KiB

gap

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

using namespace std;

long long bck = 16;

struct nod
{
    long long val,Min,Max;
};

nod divide1(long long st, long long dr)
{
    if(st > dr)
    {
        return nod{-1,-1,-1};
    }
    long long x,y;
    MinMax(st,dr,&x,&y);
    if(x==-1)
    {
        return nod{-1,-1,-1};
    }
    if(x==y)
    {
        return nod{-1,x,y};
    }
    long long mij = (x + y) >> 1;
    nod l = divide1(x+1,mij);
    nod r = divide1(mij+1,y-1);
    long long rez = -1;
    if(l.Max!=-1 && r.Min!=-1)
    {
        rez = max(rez,r.Min-l.Max);
    }
    rez = max(rez,l.val);
    rez = max(rez,r.val);
    long long Max = max(l.Max,r.Max);
    long long Min;
    if(l.Min==-1)
    {
        Min = r.Min;
    }
    else
    {
        Min = l.Min;
    }
    if(Min!=-1)
    {
        rez = max(rez,Min - x);
    }
    if(Max!=-1)
    {
        rez = max(rez,y - Max);
    }
    return nod{rez,x,y};
}

nod divide2(long long st, long long dr)
{
    if(st > dr)
    {
        return nod{-1,-1,-1};
    }
    long long x,y;
    MinMax(st,dr,&x,&y);
    if(x==-1)
    {
        return nod{-1,-1,-1};
    }
    if(x==y)
    {
        return nod{-1,x,y};
    }
    long long last = st - 1;
    long long rez = -1;
    long long Max = -1;
    for(int i=1;i<=bck;i++)
    {
        long long mij = st + ((dr - st) / bck) * i;
        if(i==bck)
        {
            mij = dr;
        }
        nod son = divide2(last+1,mij);
        last = mij;
        rez = max(rez,son.val);
        if(Max!=-1 && son.Min!=-1)
        {
            rez = max(rez,son.Min - Max);
        }
        if(son.Max!=-1)
        {
            Max = son.Max;
        }
    }
    return nod{rez,x,y};
}

long long findGap(int t, int n)
{
    if(t==1)
    {
        return divide1(1,1e18).val;
    }
    return divide2(1,1e18).val;
}

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