oj.uz

Submission #944624

# Submission time Handle Problem Language Result Execution time Memory
944624 2024-03-13T02:02:51 Z wii Gap (APIO16_gap) C++17
30 / 100
 2000 ms 524288 KB 
#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, t;
vector<ll> num;
void dnc(ll l, ll r) {
    if (l > r)
        return;

    if (t == 1) {
        ll mn = -1, mx = -1;
        if (num.size() < n) MinMax(l, r, &mn, &mx);

        if (mn == -1) return;

        num.push_back(mn);
        num.push_back(mx);

        dnc(mn + 1, mx - 1);
        return;
    }

    ll mn = -1, mx = -1;
    for (int k = 1; k <= 60; ++k) {
        MinMax(l, min(r, l + (1LL << k) - 1), &mn, &mx);
        if (mn != -1) {
            if (num.size() < n) MinMax(l, r, &mn, &mx);

            num.push_back(mn);
            if (mn != mx) num.push_back(mx);

            dnc(l + 1, mn - 1);
            dnc(mn + 1, mx - 1);
            dnc(mx + 1, r - 1);
        }

        if (r <= l + (1LL << k) - 1)
            break;
    }
}

ll findGap(int T, int N) {
    n = N; t = T;
    dnc(0, 1e18);

    sort(num.begin(), num.end());

    ll res = 0;
    for (int i = 1; i < num.size(); ++i)
        res = max(res, num[i] - num[i - 1]);

	return res;
}

Compilation message

gap.cpp: In function 'void dnc(ll, ll)':
gap.cpp:15:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |         if (num.size() < n) MinMax(l, r, &mn, &mx);
      |             ~~~~~~~~~~~^~~
gap.cpp:30:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |             if (num.size() < n) MinMax(l, r, &mn, &mx);
      |                 ~~~~~~~~~~~^~~
gap.cpp: In function 'll findGap(int, int)':
gap.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 1; i < num.size(); ++i)
      |                     ~~^~~~~~~~~~~~
gap.cpp:52:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   52 |     for (int i = 1; i < num.size(); ++i)
      |     ^~~
gap.cpp:55:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   55 |  return res;
      |  ^~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 10 ms 3984 KB Output is correct
17 Correct 9 ms 3988 KB Output is correct
18 Correct 9 ms 3992 KB Output is correct
19 Correct 9 ms 3984 KB Output is correct
20 Correct 8 ms 3984 KB Output is correct
21 Correct 34 ms 8308 KB Output is correct
22 Correct 38 ms 8340 KB Output is correct
23 Correct 34 ms 8344 KB Output is correct
24 Correct 34 ms 8372 KB Output is correct
25 Correct 31 ms 8344 KB Output is correct
26 Correct 35 ms 8228 KB Output is correct
27 Correct 34 ms 8348 KB Output is correct
28 Correct 35 ms 8312 KB Output is correct
29 Correct 34 ms 8336 KB Output is correct
30 Correct 32 ms 8348 KB Output is correct
31 Correct 1 ms 2392 KB Output is correct
32 Correct 0 ms 2392 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2392 KB Partially correct
2 Partially correct 215 ms 3520 KB Partially correct
3 Partially correct 518 ms 4544 KB Partially correct
4 Partially correct 110 ms 3020 KB Partially correct
5 Partially correct 1509 ms 20160 KB Partially correct
6 Execution timed out 3050 ms 11160 KB Time limit exceeded
7 Execution timed out 3029 ms 11364 KB Time limit exceeded
8 Execution timed out 3073 ms 12432 KB Time limit exceeded
9 Execution timed out 3043 ms 12032 KB Time limit exceeded
10 Execution timed out 3040 ms 266216 KB Time limit exceeded
11 Execution timed out 3032 ms 12812 KB Time limit exceeded
12 Execution timed out 3065 ms 12248 KB Time limit exceeded
13 Execution timed out 3032 ms 7812 KB Time limit exceeded
14 Execution timed out 3063 ms 12036 KB Time limit exceeded
15 Execution timed out 3066 ms 20376 KB Time limit exceeded
16 Execution timed out 3043 ms 9916 KB Time limit exceeded
17 Execution timed out 3060 ms 9772 KB Time limit exceeded
18 Execution timed out 3052 ms 9068 KB Time limit exceeded
19 Execution timed out 3057 ms 9404 KB Time limit exceeded
20 Execution timed out 2708 ms 524288 KB Time limit exceeded
21 Execution timed out 3049 ms 13744 KB Time limit exceeded
22 Execution timed out 3049 ms 13492 KB Time limit exceeded
23 Execution timed out 3046 ms 12432 KB Time limit exceeded
24 Execution timed out 3012 ms 14060 KB Time limit exceeded
25 Execution timed out 3063 ms 17460 KB Time limit exceeded
26 Execution timed out 3036 ms 13296 KB Time limit exceeded
27 Execution timed out 3054 ms 11840 KB Time limit exceeded
28 Execution timed out 3050 ms 11916 KB Time limit exceeded
29 Execution timed out 3006 ms 13624 KB Time limit exceeded
30 Execution timed out 2909 ms 524288 KB Time limit exceeded
31 Execution timed out 3059 ms 69572 KB Time limit exceeded
32 Execution timed out 3048 ms 266604 KB Time limit exceeded