Submission #83784

#	Time	Username	Problem	Language	Result	Execution time	Memory
83784		popovicirobert	Gap (APIO16_gap)	C++14	100 / 100	83 ms	2268 KiB

gap

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

using namespace std;

const int MAXN = (int) 1e5;
const ll INF = 1e18;

ll arr[MAXN + 1];

long long findGap(int T, int N) {
    ll A, B;
    if(T == 1) {
        ll ans = 0;
        A = 0;
        B = INF;
        for(int i = 1; i <= N - i + 1; i++) {
            ll mn, mx;
            MinMax(A, B, &arr[i], &arr[N - i + 1]);
            A = arr[i] + 1;
            B = arr[N - i + 1] - 1;
        }
        for(int i = 1; i < N; i++) {
            ans = max(ans, arr[i + 1] - arr[i]);
        }
        return ans;
    }
    MinMax(0, INF, &A, &B);
    ll dif = (B - A + N - 2) / (N - 1);
    ll cur = A, ans = dif;
    while(cur < B) {
        ll s, t, mn, mx;
        s = t = cur + 1;
        do {
            t += dif;
            if(t > B) {
                t = min(t, B);
            }
            MinMax(s, t, &mn, &mx);
            if(mx == -1) {
                continue;
            }
            else {
                break;
            }
        }while(1);
        ans = max(ans, mn - cur);
        dif = max(dif, ans);
        cur = mx;
        //cerr << cur << " ";
    }
	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:19:16: warning: unused variable 'mn' [-Wunused-variable]
             ll mn, mx;
                ^~
gap.cpp:19:20: warning: unused variable 'mx' [-Wunused-variable]
             ll mn, mx;
                    ^~

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