Submission #720847

#	Time	Username	Problem	Language	Result	Execution time	Memory
720847		Joshc	Gap (APIO16_gap)	C++11	38.57 / 100	56 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) {
        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;
            bool reachedEnd = false;
            int iterations = 0;
            while (true) {
                iterations++;
                MinMax(l, min(INF, l+sz), &p, &q);
                if (l+sz >= INF && p == -1) {
                    reachedEnd = true;
                    break;
                }
                if (q != l) break;
                sz *= 2;
            }
            if (iterations > 1) {
                MinMax(l+1, q, &p, &q);
                res = max(res, p-l);
            }
            l = q;
            if (reachedEnd) break;
        }
        return res;
    }
}

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