제출 #720859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720859		Joshc	Gap (APIO16_gap)	C++11	30 / 100	44 ms	1872 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const ll INF = 1e18;
 
ll findGap(int T, int N) {
    if (T == 1 || N <= 16) {
        vector<ll> a(N);
        int l = 0, r = N-1;
        ll p = -1, q = INF+1;
        while (l <= r) {
            MinMax(p+1, q-1, &p, &q);
            a[l++] = p;
            a[r--] = q;
        }
        ll res = 0;
        for (int i=1; i<N; i++) res = max(res, a[i] - a[i-1]);
        return res;
    } else {
        ll res = 1, l = 0, big, p, q;
        MinMax(0, INF, &l, &big);
        while (l < big) {
            ll sz = res+1;
            bool reachedEnd = false;
            while (true) {
                MinMax(l+1, min(INF, l+sz), &p, &q);
                if (l+sz >= INF && p == -1) {
                    reachedEnd = true;
                    break;
                }
                if (q != l) break;
                sz *= 2;
            }
            MinMax(l+1, q, &p, &q);
            //printf("Test: %lld %lld %lld\n", l, p, q);
            res = max(res, p-l);
            l = q;
            if (reachedEnd) break;
        }
        return res;
    }
}

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