oj.uz

Submission #614755

# Submission time Handle Problem Language Result Execution time Memory
614755 2022-07-31T04:45:05 Z KoD Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 47880 KB 
#include <bits/stdc++.h>

using std::vector;

template <class F> struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

vector<int> solve(const int N, const int M) {
    vector<int> ret;
    const auto gen = [&](const int len) {
        vector<int> state(len + 1), order;
        order.reserve(len + 1);
        const auto dfs = fixed([&](auto&& dfs, const int u) -> bool {
            if (state[u] == 1) return true;
            if (state[u] == -1) return false;
            state[u] = -1;
            if (u >= M and !dfs(u - M)) return false;
            if (u + N <= len and !dfs(u + N)) return false;
            order.push_back(u);
            state[u] = 1;
            return true;
        });
        for (int i = 0; i <= len; ++i) {
            if (!dfs(i)) return false;
        }
        vector<int> rank(len + 1);
        for (int i = 0; i <= len; ++i) {
            rank[order[i]] = i;
        }
        ret.resize(len);
        for (int i = 0; i < len; ++i) {
            ret[i] = rank[i + 1] - rank[i];
        }
        return true;
    };
    int ok = 0, ng = N + M;
    while (ng - ok > 1) {
        const int md = (ok + ng) / 2;
        (gen(md) ? ok : ng) = md;   
    }
    return ret;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    while (T--) {
        int N, M;
        std::cin >> N >> M;
        const auto A = solve(N, M);
        std::cout << A.size() << '\n';
        for (int i = 0; i < (int)A.size(); ++i) {
            if (i > 0) std::cout << ' ';
            std::cout << A[i];
        }
        std::cout << '\n';
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 324 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 324 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 212 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 320 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 4 ms 468 KB Ok
7 Correct 26 ms 1108 KB Ok
8 Correct 11 ms 672 KB Ok
9 Correct 29 ms 1236 KB Ok
10 Correct 17 ms 808 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 288 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 324 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 320 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 286 ms 10380 KB Ok
7 Correct 263 ms 10760 KB Ok
8 Correct 587 ms 14184 KB Ok
9 Correct 399 ms 12476 KB Ok
10 Correct 208 ms 6116 KB Ok
11 Correct 324 ms 13516 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 324 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 324 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 316 KB Ok
14 Correct 0 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 0 ms 212 KB Ok
18 Correct 1 ms 212 KB Ok
19 Correct 1 ms 288 KB Ok
20 Correct 1 ms 212 KB Ok
21 Correct 1 ms 324 KB Ok
22 Correct 1 ms 212 KB Ok
23 Correct 1 ms 212 KB Ok
24 Correct 4 ms 340 KB Ok
25 Correct 4 ms 340 KB Ok
26 Correct 6 ms 340 KB Ok
27 Correct 5 ms 324 KB Ok
28 Correct 4 ms 340 KB Ok
29 Correct 3 ms 340 KB Ok
30 Correct 3 ms 340 KB Ok
31 Correct 4 ms 408 KB Ok
32 Correct 4 ms 392 KB Ok
33 Correct 5 ms 340 KB Ok
34 Correct 9 ms 576 KB Ok
35 Correct 10 ms 568 KB Ok
36 Correct 10 ms 596 KB Ok
37 Correct 10 ms 596 KB Ok
38 Correct 10 ms 608 KB Ok
39 Correct 9 ms 572 KB Ok
40 Correct 10 ms 608 KB Ok
41 Correct 9 ms 568 KB Ok
42 Correct 10 ms 584 KB Ok
43 Correct 9 ms 548 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 324 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 324 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 320 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 4 ms 468 KB Ok
19 Correct 26 ms 1108 KB Ok
20 Correct 11 ms 672 KB Ok
21 Correct 29 ms 1236 KB Ok
22 Correct 17 ms 808 KB Ok
23 Correct 1 ms 316 KB Ok
24 Correct 0 ms 212 KB Ok
25 Correct 1 ms 212 KB Ok
26 Correct 1 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 1 ms 288 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 324 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 4 ms 340 KB Ok
35 Correct 4 ms 340 KB Ok
36 Correct 6 ms 340 KB Ok
37 Correct 5 ms 324 KB Ok
38 Correct 4 ms 340 KB Ok
39 Correct 3 ms 340 KB Ok
40 Correct 3 ms 340 KB Ok
41 Correct 4 ms 408 KB Ok
42 Correct 4 ms 392 KB Ok
43 Correct 5 ms 340 KB Ok
44 Correct 9 ms 576 KB Ok
45 Correct 10 ms 568 KB Ok
46 Correct 10 ms 596 KB Ok
47 Correct 10 ms 596 KB Ok
48 Correct 10 ms 608 KB Ok
49 Correct 9 ms 572 KB Ok
50 Correct 10 ms 608 KB Ok
51 Correct 9 ms 568 KB Ok
52 Correct 10 ms 584 KB Ok
53 Correct 9 ms 548 KB Ok
54 Correct 194 ms 3388 KB Ok
55 Correct 198 ms 3856 KB Ok
56 Correct 209 ms 3784 KB Ok
57 Correct 159 ms 2928 KB Ok
58 Correct 196 ms 3152 KB Ok
59 Correct 163 ms 2776 KB Ok
60 Correct 164 ms 2880 KB Ok
61 Correct 156 ms 2892 KB Ok
62 Correct 191 ms 3392 KB Ok
63 Correct 165 ms 3080 KB Ok
64 Correct 208 ms 3656 KB Ok
65 Correct 179 ms 3668 KB Ok
66 Correct 188 ms 3256 KB Ok
67 Correct 177 ms 3128 KB Ok
68 Correct 172 ms 3000 KB Ok
69 Correct 398 ms 11052 KB Ok
70 Correct 394 ms 11796 KB Ok
71 Correct 370 ms 11244 KB Ok
72 Correct 381 ms 11136 KB Ok
73 Correct 387 ms 11248 KB Ok
74 Correct 373 ms 11140 KB Ok
75 Correct 385 ms 10696 KB Ok
76 Correct 397 ms 11444 KB Ok
77 Correct 336 ms 10752 KB Ok
78 Correct 374 ms 11180 KB Ok
79 Correct 372 ms 11352 KB Ok
80 Correct 363 ms 11636 KB Ok
81 Correct 386 ms 11460 KB Ok
82 Correct 363 ms 11396 KB Ok
83 Correct 339 ms 10840 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 324 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 324 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 320 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 4 ms 468 KB Ok
19 Correct 26 ms 1108 KB Ok
20 Correct 11 ms 672 KB Ok
21 Correct 29 ms 1236 KB Ok
22 Correct 17 ms 808 KB Ok
23 Correct 1 ms 316 KB Ok
24 Correct 0 ms 212 KB Ok
25 Correct 1 ms 212 KB Ok
26 Correct 1 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 1 ms 288 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 324 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 1 ms 212 KB Ok
35 Correct 1 ms 320 KB Ok
36 Correct 1 ms 212 KB Ok
37 Correct 1 ms 212 KB Ok
38 Correct 1 ms 212 KB Ok
39 Correct 286 ms 10380 KB Ok
40 Correct 263 ms 10760 KB Ok
41 Correct 587 ms 14184 KB Ok
42 Correct 399 ms 12476 KB Ok
43 Correct 208 ms 6116 KB Ok
44 Correct 324 ms 13516 KB Ok
45 Correct 4 ms 340 KB Ok
46 Correct 4 ms 340 KB Ok
47 Correct 6 ms 340 KB Ok
48 Correct 5 ms 324 KB Ok
49 Correct 4 ms 340 KB Ok
50 Correct 3 ms 340 KB Ok
51 Correct 3 ms 340 KB Ok
52 Correct 4 ms 408 KB Ok
53 Correct 4 ms 392 KB Ok
54 Correct 5 ms 340 KB Ok
55 Correct 9 ms 576 KB Ok
56 Correct 10 ms 568 KB Ok
57 Correct 10 ms 596 KB Ok
58 Correct 10 ms 596 KB Ok
59 Correct 10 ms 608 KB Ok
60 Correct 9 ms 572 KB Ok
61 Correct 10 ms 608 KB Ok
62 Correct 9 ms 568 KB Ok
63 Correct 10 ms 584 KB Ok
64 Correct 9 ms 548 KB Ok
65 Correct 194 ms 3388 KB Ok
66 Correct 198 ms 3856 KB Ok
67 Correct 209 ms 3784 KB Ok
68 Correct 159 ms 2928 KB Ok
69 Correct 196 ms 3152 KB Ok
70 Correct 163 ms 2776 KB Ok
71 Correct 164 ms 2880 KB Ok
72 Correct 156 ms 2892 KB Ok
73 Correct 191 ms 3392 KB Ok
74 Correct 165 ms 3080 KB Ok
75 Correct 208 ms 3656 KB Ok
76 Correct 179 ms 3668 KB Ok
77 Correct 188 ms 3256 KB Ok
78 Correct 177 ms 3128 KB Ok
79 Correct 172 ms 3000 KB Ok
80 Correct 398 ms 11052 KB Ok
81 Correct 394 ms 11796 KB Ok
82 Correct 370 ms 11244 KB Ok
83 Correct 381 ms 11136 KB Ok
84 Correct 387 ms 11248 KB Ok
85 Correct 373 ms 11140 KB Ok
86 Correct 385 ms 10696 KB Ok
87 Correct 397 ms 11444 KB Ok
88 Correct 336 ms 10752 KB Ok
89 Correct 374 ms 11180 KB Ok
90 Correct 372 ms 11352 KB Ok
91 Correct 363 ms 11636 KB Ok
92 Correct 386 ms 11460 KB Ok
93 Correct 363 ms 11396 KB Ok
94 Correct 339 ms 10840 KB Ok
95 Correct 461 ms 7972 KB Ok
96 Correct 646 ms 11612 KB Ok
97 Correct 572 ms 9012 KB Ok
98 Correct 496 ms 7480 KB Ok
99 Correct 485 ms 8692 KB Ok
100 Correct 538 ms 9276 KB Ok
101 Correct 597 ms 10400 KB Ok
102 Correct 645 ms 10824 KB Ok
103 Correct 609 ms 9868 KB Ok
104 Correct 740 ms 10888 KB Ok
105 Correct 625 ms 10660 KB Ok
106 Correct 566 ms 10508 KB Ok
107 Correct 658 ms 11232 KB Ok
108 Correct 632 ms 11720 KB Ok
109 Correct 580 ms 9904 KB Ok
110 Correct 1849 ms 45292 KB Ok
111 Execution timed out 2055 ms 47880 KB Time limit exceeded
112 Halted 0 ms 0 KB -