Submission #1187910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187910		Warinchai	Gap (APIO16_gap)	C++20	46.81 / 100	52 ms	5908 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;

long long ar[100005];
set<long long>s;

long long sub1(long long N){
    for(int i=1;i<=N;i++)ar[i]=0;
    long long l=0,r=1e18;
    long long ll=1,rr=N;
    while(ll<=rr){
        MinMax(l,r,&l,&r);
        ar[ll]=l,ar[rr]=r;
        l++,r--;
        ll++,rr--;
    }
    long long ans=0;
    for(int i=1;i<N;i++)ans=max(ans,ar[i+1]-ar[i]);
    return ans;
}

void solve(long long l,long long r){
    if(l>r)return;
    if(l==r){
        MinMax(l,r,&l,&r);
        if(l==-1)return;
        else return void(s.insert(l));
    }
    long long m1=(l+r)/2;
    long long m2=(l+r)/2+1;
    MinMax(l,m1,&l,&m1);
    if(m2<=r)MinMax(m2,r,&m2,&r);
    if(l!=-1)s.insert(l);
    if(m1!=l)s.insert(m1);
    if(r!=-1)s.insert(m2);
    if(m2!=r)s.insert(r);
    if(l!=-1)solve(l+1,m1-1);
    if(r!=-1)solve(m2+1,r-1);
}

long long sub2(int N){
    if(N<=3)return sub1(N);
    solve(0,1e18);
    auto x=s.begin();
    auto y=next(s.begin());
    long long ans=0;
    while(y!=s.end()){
        ans=max(ans,(*y)-(*x));
        x=next(x);
        y=next(y);
    }
    return ans;
}

long long findGap(int T, int N)
{
    if(T==1)return sub1(N);
	return sub2(N);
}

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