제출 #1218507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218507		tapilyoca	Gap (APIO16_gap)	C++20	0 / 100	2112 ms	589824 KiB

gap

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

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using pll = pair<ll,ll>;
#define pb push_back


long long findGap(int T, int N) {
    if(T == 1) {
        vll a;
        ll lp = 1, rp = 1e18;
        ll mn = -1, mx = 1e18;

        while(a.size() != N) {
            MinMax(lp,rp,&mn,&mx);
            a.pb(mn);
            a.pb(mx);
            lp = mn + 1;
            rp = mx - 1;
        }

        sort(a.begin(),a.end());
        ll ans = -1;
        for(int i = 1; i < N; i++) {
            ans = max(ans, a[i] - a[i-1]);
        }
        return ans;
    }
    
    else {
        vll a;
        ll lp = 1, rp = 1e18;
        ll mn = -1, mx = 1e18;

        MinMax(lp,rp,&mn,&mx);
        ll largest = mx;
        a.pb(mn);
        a.pb(mx);
        ll L = (mx - mn + N - 2)/(N - 1);

        // cerr << "Gap size: " << L << endl;
        
        for(int i = mn; i <= largest; i += L+1) {
            MinMax(i,i+L,&mn,&mx);
            // cerr << "Querah " << i << " " << i+L << endl;
            if(mn != -1) {
                a.pb(mn);
                if(mn != mx) a.pb(mx);
            }
        }

        sort(a.begin(),a.end());
        ll ans = 0;
        for(int i = 1; i < a.size(); i++) {
            ans = max(ans, a[i] - a[i-1]);
        }
        return ans;
    }
}

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