oj.uz

답안 #564236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
564236 2022-05-18T19:26:49 Z Ooops_sorry Gap (APIO16_gap) C++14
0 / 100
 375 ms 5824 KB 
#include<bits/stdc++.h>
#ifndef LOCAL
    #include "gap.h"
#endif

#define ll long long

using namespace std;

#ifdef LOCAL
    static void my_assert(int k){ if (!k) exit(1); }

    static int subtask_num, N;
    static long long A[100001];
    static long long call_count;
    void MinMax(long long s, long long t, long long *mn, long long *mx)
    {
        int lo = 1, hi = N, left = N+1, right = 0;
        my_assert(s <= t && mn != NULL && mx != NULL);
        while (lo <= hi){
            int mid = (lo+hi)>>1;
            if (A[mid] >= s) hi = mid - 1, left = mid;
            else lo = mid + 1;
        }
        lo = 1, hi = N;
        while (lo <= hi){
            int mid = (lo+hi)>>1;
            if (A[mid] <= t) lo = mid + 1, right = mid;
            else hi = mid - 1;
        }
        if (left > right) *mn = *mx = -1;
        else{
            *mn = A[left];
            *mx = A[right];
        }
        if (subtask_num == 1) call_count++;
        else if (subtask_num == 2) call_count += right-left+2;
    }
#endif // LOCAL

set<int> st;
const ll INF = 1e18;

mt19937_64 rnd(51);

void solve(ll l, ll r) {
    if (l > r) {
        return;
    }
    ll len = r - l + 1;
    ll mid = l + rnd() % len, mn, mx;
    if (rnd() % 2) {
        MinMax(mid, r, &mn, &mx);
        if (mn != -1) {
            st.insert(mn);
            st.insert(mx);
            solve(mn + 1, mx - 1);
        }
        solve(l, mid - 1);
    } else {
        MinMax(l, mid, &mn, &mx);
        if (mn != -1) {
            st.insert(mn);
            st.insert(mx);
            solve(mn + 1, mx - 1);
        }
        solve(mid + 1, r);
    }
}

long long findGap(int t, int n) {
    solve(0, INF);
    ll last = -1, res = 0;
    for (auto to : st) {
        if (last != -1) {
            res = max(res, abs(last - to));
        }
        last = to;
    }
    return res;
}

#ifdef LOCAL
    int main()
    {
        FILE *in = stdin, *out = stdout;
        my_assert(2 == fscanf(in, "%d%d", &subtask_num, &N));
        my_assert(1 <= subtask_num && subtask_num <= 2);
        my_assert(2 <= N && N <= 100000);
        for (int i=1;i<=N;i++) my_assert(1 == fscanf(in, "%lld", A+i));
        for (int i=1;i<N;i++) my_assert(A[i] < A[i+1]);
        fprintf(out, "%lld\n", findGap(subtask_num, N));
        fprintf(out, "%lld\n", call_count);
    }

#endif

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Incorrect 0 ms 208 KB Output isn't correct
3 Incorrect 0 ms 208 KB Output isn't correct
4 Incorrect 1 ms 208 KB Output isn't correct
5 Incorrect 0 ms 208 KB Output isn't correct
6 Incorrect 1 ms 208 KB Output isn't correct
7 Incorrect 1 ms 208 KB Output isn't correct
8 Incorrect 1 ms 208 KB Output isn't correct
9 Incorrect 1 ms 208 KB Output isn't correct
10 Incorrect 0 ms 208 KB Output isn't correct
11 Incorrect 3 ms 336 KB Output isn't correct
12 Incorrect 4 ms 336 KB Output isn't correct
13 Incorrect 3 ms 336 KB Output isn't correct
14 Incorrect 4 ms 396 KB Output isn't correct
15 Incorrect 3 ms 336 KB Output isn't correct
16 Incorrect 90 ms 1608 KB Output isn't correct
17 Incorrect 71 ms 1608 KB Output isn't correct
18 Incorrect 70 ms 1628 KB Output isn't correct
19 Incorrect 82 ms 1564 KB Output isn't correct
20 Incorrect 20 ms 1616 KB Output isn't correct
21 Incorrect 313 ms 5784 KB Output isn't correct
22 Incorrect 351 ms 5788 KB Output isn't correct
23 Incorrect 292 ms 5780 KB Output isn't correct
24 Incorrect 328 ms 5708 KB Output isn't correct
25 Incorrect 175 ms 5804 KB Output isn't correct
26 Incorrect 321 ms 5704 KB Output isn't correct
27 Incorrect 303 ms 5748 KB Output isn't correct
28 Incorrect 289 ms 5756 KB Output isn't correct
29 Incorrect 375 ms 5668 KB Output isn't correct
30 Incorrect 63 ms 5744 KB Output isn't correct
31 Incorrect 1 ms 208 KB Output isn't correct
32 Incorrect 1 ms 208 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Incorrect 1 ms 220 KB Output isn't correct
3 Incorrect 2 ms 208 KB Output isn't correct
4 Incorrect 1 ms 208 KB Output isn't correct
5 Partially correct 0 ms 208 KB Partially correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Incorrect 1 ms 208 KB Output isn't correct
8 Incorrect 1 ms 336 KB Output isn't correct
9 Incorrect 1 ms 208 KB Output isn't correct
10 Partially correct 0 ms 208 KB Partially correct
11 Incorrect 4 ms 464 KB Output isn't correct
12 Incorrect 4 ms 336 KB Output isn't correct
13 Incorrect 3 ms 336 KB Output isn't correct
14 Incorrect 4 ms 356 KB Output isn't correct
15 Incorrect 2 ms 336 KB Output isn't correct
16 Incorrect 72 ms 1628 KB Output isn't correct
17 Incorrect 73 ms 1600 KB Output isn't correct
18 Incorrect 61 ms 1556 KB Output isn't correct
19 Incorrect 78 ms 1608 KB Output isn't correct
20 Partially correct 20 ms 1692 KB Partially correct
21 Incorrect 333 ms 5788 KB Output isn't correct
22 Incorrect 321 ms 5704 KB Output isn't correct
23 Incorrect 278 ms 5728 KB Output isn't correct
24 Incorrect 326 ms 5800 KB Output isn't correct
25 Incorrect 158 ms 5704 KB Output isn't correct
26 Incorrect 300 ms 5720 KB Output isn't correct
27 Incorrect 292 ms 5816 KB Output isn't correct
28 Incorrect 281 ms 5824 KB Output isn't correct
29 Incorrect 296 ms 5668 KB Output isn't correct
30 Partially correct 64 ms 5704 KB Partially correct
31 Incorrect 1 ms 208 KB Output isn't correct
32 Incorrect 1 ms 208 KB Output isn't correct