Submission #1204972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204972		a.pendov	Gap (APIO16_gap)	C++20	30 / 100	43 ms	2240 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
const long long MAX1=LLONG_MAX;

inline long long max1(long long a,long long b)
{
    if(a>b)return a;
    return b;
}

long long solve1(long long N)
{
    long long l=0,r=MAX1,a,b,ans=0;
    vector<long long> v;

    for(long long i=0;i<N;i+=2)
    {
        MinMax(l,r,&a,&b);
        v.push_back(a);
        if(a!=b)v.push_back(b);
        l=a+1;
        r=b-1;
    }

    sort(v.begin(),v.end());

    for(long long i=1;i<N;i++)
    {
        ans=max1(ans,v[i]-v[i-1]);
    }

    return ans;
}

long long solve2(long long N)
{
    long long a,b,las,ans=0,x,y;
    MinMax(0,MAX1,&a,&b);
    long long k=(b-a+N-1)/(N-1);
    las=a;
    for(long long i=a;i<b;i+=k)
    {
        MinMax(i,i+k-1,&x,&y);
        if(x==-1)continue;
        ans=max1(ans,x-las);
        las=y;
    }

    return ans;
}

long long findGap(int T, int N)
{
    if(T==1)return solve1(N);
    return solve2(N);
}

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