제출 #1133021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133021		t9unkubj	Gap (APIO16_gap)	C++20	53.51 / 100	45 ms	4796 KiB

gap

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#include"gap.h"
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;

/*long long findGap(int T, int N);
namespace judge{
    int n;
    vc<ll>a;
    int cnt=0;
    void MinMax(ll s,ll t,ll*mn,ll*mx){
        assert(s<=t);
        auto itr=lower_bound(all(a),s)-a.begin();
        auto it2=upper_bound(all(a),t)-a.begin();
        cnt+=it2-itr;
        if(itr<n&&a[itr]<=t)*mn=a[itr];
        else *mn=-1;
        if(it2>0&&a[it2-1]>=s)*mx=a[it2-1];
        else *mx=-1;
    }
    void checker(int N,vc<ll>A){
        n=N,a=A;
        cnt=0;
        ll D=0;
        rep(i,n-1)chmax(D,a[i+1]-a[i]);
        if(D!=findGap(2,n)){
            dbg(D);
            dbg(n,A);
            dbg(findGap(2,n));
            assert(0);
        }
        assert(cnt<=3*n);
        dbg("OKOK"s);
    }
    mt19937 mt;
    void stress(){
        while(1){
            int n=mt()%(int)10+1;
            vc<ll>a(n);
            rep(i,n)a[i]=mt();
            sort(all(a));
            a.erase(unique(all(a)),a.end());
            n=a.size();
            checker(n,a);
        }
    }
    void run(){
        cin>>n;
        a.resize(n);
        rep(i,n)cin>>a[i];
        checker(n,a);
    }
};
using namespace judge;*/
long long findGap(int T, int N){
    int n=N;
    vc<ll>l(n+1),r(n+1);
    ll*a=new ll();
    ll*b=new ll();
    MinMax(0,2e18,a,b);
    l[0]=*a,r[0]=*b;
    delete a;
    delete b;
    ll W=r[0]-l[0];
    ll per=(W+n-1)/n;

    for(int i=0;i<n;i++){
        ll*a=new ll();
        ll*b=new ll();
        MinMax(per*i+l[0],per*(i+1)+l[0],a,b);
        
        l[i+1]=*a,r[i+1]=*b;
        delete a;
        delete b;
    }
    vc<ll>vs;
    rep(i,n){
        if(l[i+1]!=-1)vs.push_back(l[i+1]);
        if(r[i+1]!=-1)vs.push_back(r[i+1]);
    }
    vs.push_back(l[0]);
    vs.push_back(r[0]);
    sort(all(vs));
    ll ans=0;
    rep(i,vs.size()-1){
        chmax(ans,vs[i+1]-vs[i]);
    }
    return ans;
}
//int main(){judge::stress();}

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