제출 #745419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745419		AirCircles	Gap (APIO16_gap)	C++17	78.54 / 100	57 ms	1864 KiB

gap

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

//void MinMax(s,t,&mn,&mx)

long long findGap(int TT, int n){
    if(TT==1){
        //long long s,t,&mn,&mx;
        vector<long long>dn(n);
        MinMax(0,1000000000000000000LL,&dn[0],&dn[n-1]);
        for(int i=1;i<n/2;i++){
            MinMax(dn[i-1]+1,dn[n-i]-1,&dn[i],&dn[n-i-1]);
        }
        if(n%2==1){
            MinMax(dn[n/2-1]+1,dn[n/2+1]-1,&dn[n/2],&dn[n/2]);
        }
        long long mn=0LL;
        for(int i=0;i<n-1;i++){
            mn=max(mn,dn[i+1]-dn[i]);
        }
        return mn;
    }else{
        long long a,b;
        MinMax(0,1000000000000000000LL,&a,&b);
        long long d=(b-a-1)/(n-1);
        long long x=(b-a-1)-d*(n-1);
        long long y=n-1-x;
        long long ma=0,xx=a,p=a+1;//pointer
        for(int i=0;i<n-1;i++){
            long long mn,mx;
            if(i<y){
                MinMax(p,p+d,&mn,&mx);
                p+=d;
            }else{
                MinMax(p,p+d+1,&mn,&mx);
                p+=d+1;
            }
            if(mn!=-1){
                ma=max(ma,mn-xx);
                xx=mx;
            }
        }
        ma=max(ma,b-xx);
        return ma;
    }
}

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