제출 #842301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842301		popovicirobert	Gap (APIO16_gap)	C++14	56.31 / 100	46 ms	3116 KiB

gap

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

constexpr ll INF =  1e18;

vector<ll> arr;

#ifdef HOME

void MinMax(ll a, ll b, ll* mn, ll* mx) {
    *mn = INF;
    *mx = -INF;
    for (auto itr : arr) {
        if (itr >= a && itr <= b) {
            *mn = min(*mn, itr);
            *mx = max(*mx, itr);
        }
    }
    if (*mn == INF) {
        *mn = -1;
    }
    if (*mx == -INF) {
        *mx = -1;
    }
}

#else
#include "gap.h"
#endif

pair<ll, ll> Query(ll a, ll b) {
    ll mn, mx;
    MinMax(a, b, &mn, &mx);
    return {mn, mx};
}

ll findGap(int T, int N) {
    pair<ll, ll> res = Query(0, INF);
    
    ll a1 = res.first;
    ll an = res.second;
    ll step = (an - a1 + N - 2) / (N - 1);

    ll answer = 0;

    ll curr = a1;
    while (curr < an) {
        int x = 0;
        do {
            x++;
            res = Query(curr + 1, curr + step * x);
            if (res.second != -1) {
                break;
            }
        } while (true);

        answer = max(answer, res.first - curr);
        curr = res.second;
    }

    return answer;
}

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