Submission #160227

#	Time	Username	Problem	Language	Result	Execution time	Memory
160227		BlueDiamond	Gap (APIO16_gap)	C++14	42.89 / 100	157 ms	2096 KiB

gap

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

using namespace std;

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

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 = (mn + mx) / 2;
        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:31:20: warning: unused variable 'ans' [-Wunused-variable]
                 ll ans = 0;
                    ^~~
gap.cpp:35:42: warning: unused variable 'ans' [-Wunused-variable]
                 ll s = 0, t = (ll) 1e18, ans = 0;
                                          ^~~

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