제출 #1199238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199238		vnedu	Gap (APIO16_gap)	C++17	100 / 100	42 ms	2320 KiB

gap

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

long long mn,mx;
vector<long long> v;
long long findGap(int T, int n)
{
    if(T==1)
    {
        MinMax(-1e18,1e18,&mn,&mx);
        v.push_back(mn);
        v.push_back(mx);
        long long l=mn,r=mx;
        ++l,--r;
        int cnt=2;
        while(1)
        {
            if(cnt==n) break;
            long long nl,nr;
            MinMax(l,r,&nl,&nr);
            if(nl==-1) break;
            v.push_back(nl),++cnt;
            if(nr!=nl) v.push_back(nr),++cnt;
            l=nl+1;
            r=nr-1;
            if(l>r) break;
        }
        sort(v.begin(),v.end());
        long long ans=0;
        for(int i=1;i<n;++i) ans=max(ans,v[i]-v[i-1]);
        return ans;
    }
    else
    {
        MinMax(-1e18,1e18,&mn,&mx);
        long long a1=mn,an=mx,l=an-a1,x=(l+n-1)/(n-1),lst=a1,ans=0,st=a1+1;
        while(st<=an)
        {
            MinMax(st,st+x-1,&mn,&mx);
            if(mn!=-1)
            {
                ans=max(ans,mn-lst);
                lst=mx;
            }
            st+=x;
        }
        return ans;
    }
}

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