Submission #110742

#	Time	Username	Problem	Language	Result	Execution time	Memory
110742		TAISA_	Gap (APIO16_gap)	C++14	0 / 100	62 ms	1784 KiB

gap

#include <bits/stdc++.h>
#include "gap.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 N=n;
    ll mi, ma;
    ll INF = 100000000000000000LL;
    MinMax(0LL, INF, &mi, &ma);
    if(N == ma - mi + 1LL) {
        return 1LL;
    }
    ll l = (ma - mi + 1LL) / (N + 1LL) + 1LL, m = (ma - mi + 1LL) % (N + 1LL);
    ll b = mi, res = 0, t = mi, s = 0;
    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;
            }
            b = ma;
        }
        t += nl;
    }
    return res;
}
/*int main() {
    cout << findGap(0, 4) << endl;
}*/

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