Submission #160233

#	Time	Username	Problem	Language	Result	Execution time	Memory
160233		BlueDiamond	Gap (APIO16_gap)	C++14	30 / 100	123 ms	3704 KiB

gap

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

using namespace std;

typedef long long ll;
ll hidden[(int) 1e5 + 7];
int cur;

mt19937 rnd(228);

ll rng() {
        ll a = 0;
        for (ll x = 0; x <= 60; x++)
                if (rnd())
                        a += (1LL << x);
        return a;
}

ll get(ll x, ll y) {
        ll len = y - x + 1;
        return x + rng() % len;
}

void run(ll x, ll y) {
        if (x > y)
                return;
        ll mn, mx;
        MinMax(x, y, &mn, &mx);
        if (mn == -1 && mx == -1)
                return;
        if (mn == mx) {
                hidden[++cur] = mn;
                return;
        }
        hidden[++cur] = mn;
        ll mid = get(mn, mx);
        run(mn + 1, mid);
        run(mid + 1, mx - 1);
        hidden[++cur] = mx;
}


ll findGap(int T, int N) {
        if (T == 2) {
                ll ans = 0;
                run(0, (ll) 1e18);
        } else {
                int i = 1, j = N;
                ll s = 0, t = (ll) 1e18, ans = 0;
                while (i <= j) {
                        ll mn, mx;
                        MinMax(s, t, &mn, &mx);
                        hidden[i] = mn;
                        hidden[j] = mx;
                        s = mn + 1;
                        t = mx - 1;
                        i++;
                        j--;
                }
        }
        ll ans = 0;
        for (int i = 1; i < N; i++)
                ans = max(ans, hidden[i + 1] - hidden[i]);
        return ans;
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:46:20: warning: unused variable 'ans' [-Wunused-variable]
                 ll ans = 0;
                    ^~~
gap.cpp:50:42: warning: unused variable 'ans' [-Wunused-variable]
                 ll s = 0, t = (ll) 1e18, ans = 0;
                                          ^~~

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