Submission #1187937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187937		Warinchai	Gap (APIO16_gap)	C++20	30 / 100	66 ms	5704 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;
}

long long sub2(int N){
    s.clear();
    long long l=0,r=1e18;
    MinMax(l,r,&l,&r);
    s.insert(l);
    s.insert(r);
    long long gap=((r-l-1)/(N-2))+1;
    long long st=l+1;
    assert((r-l-1)/gap<=N);
    while(st<r){
        long long ll=st,rr=st+gap-1;
        MinMax(ll,rr,&ll,&rr);
        if(ll!=-1)s.insert(ll);
        if(rr!=ll)s.insert(rr);
        st+=gap;
    }
    long long ans=0;
    auto x=s.begin();
    auto y=next(s.begin());
    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: 0 / 70