제출 #110756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110756		TAISA_	Gap (APIO16_gap)	C++14	100 / 100	88 ms	2740 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*void MinMax(ll l, ll r, ll& mi, ll& ma) {
    cout << l << " " << r << endl;
    cin >> mi >> ma;
}*/
ll findGap(int T, int n) {
    ll INF = 1000000000000000000LL;
    ll N = n;
    ll mi, ma;
    MinMax(0LL, INF, &mi, &ma);
    if(N == ma - mi + 1LL) {
        return 1LL;
    }
    if(T == 1) {
        vector<ll> v1, v2;
        v1.push_back(mi);
        v2.push_back(ma);
        for(int i = 0; i < N / 2 - 1; i++) {
            MinMax(mi + 1LL, ma - 1LL, &mi, &ma);
            v1.push_back(mi);
            v2.push_back(ma);
        }
        if(N % 2) {
            MinMax(mi + 1LL, ma - 1LL, &mi, &ma);
            v1.push_back(mi);
        }
        reverse(v2.begin(), v2.end());
        for(auto e : v2) {
            v1.push_back(e);
        }
        ll res = 0;
        for(int i = 1; i < N; i++) {
            res = max(res, v1[i] - v1[i - 1]);
        }
        return res;
    } else {
        ll l = (ma - mi + 1LL) / N + 1LL, m = (ma - mi + 1LL) % N;
        ll b = mi, res = 0, t = mi, s = 0, maa = ma;
        bool f = false;
        for(int i = 0; i < N - 1; i++) {
            ll nl = l - (i >= m);
            MinMax(t, t + nl - 1LL, &mi, &ma);
            if(mi == -1) {
                if(f) {
                    s += nl;
                } else {
                    s += nl + (t - b);
                    f = true;
                }
            } else {
                if(f) {
                    s += mi - t;
                    res = max(res, s);
                    s = 0;
                    f = false;
                } else {
                    res = max(res, mi - b);
                }
                b = ma;
            }
            t += nl;
        }
        MinMax(t, maa - 1, &mi, &ma);
        if(mi == -1) {
            if(f) {
                s += maa - t;
                res = max(res, s);
            } else {
                res = max(res, maa - b);
            }
        } else {
            if(f) {
                s += mi - t;
                res = max(res, s);
            } else {
                res = max(res, mi - b);
            }
        }
        return res;
    }
}
/*int main() {
    cout << findGap(0, 4) << endl;
}*/

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