제출 #861194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861194		Dec0Dedd	Gap (APIO16_gap)	C++14	100 / 100	45 ms	3876 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

typedef long long ll;

const ll INF = 1e18;

ll solve1(int n) {
    ll a[n]={};

    ll lf=-1, rf=INF+1, lp=0, rp=n-1;
    while (lp <= rp) {
        ll mn, mx; MinMax(lf+1, rf-1, &mn, &mx);
        if (mn == -1) break;
        a[lp++]=mn, a[rp--]=mx;
        lf=mn, rf=mx;
    }

    ll ans=1;
    for (int i=0; i<n-1; ++i) ans=max(ans, a[i+1]-a[i]);
    return ans;
}

ll solve2(int n) {
    ll lf, rf; MinMax(0, INF, &lf, &rf);
    if (n == 2) return rf-lf;

    ll ans=(rf-lf)/n, d=(rf-lf+(n-2))/(n-1), lst=lf;
    while (lf < rf-1) {
        ll mn, mx; MinMax(lf+1, lf+d, &mn, &mx);
        if (mn != -1) ans=max(ans, mn-lst), lst=mx;
        lf+=d;
    } return ans;
}

ll findGap(int t, int n) {
    if (t == 1) return solve1(n);
    return solve2(n);
}

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