oj.uz

Submission #614824

# Submission time Handle Problem Language Result Execution time Memory
614824 2022-07-31T05:05:01 Z KoD Nice sequence (IZhO18_sequence) C++17
100 / 100
 460 ms 44676 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) {
    const int len = N + M - 1 - std::gcd(N, M);
    vector<char> done(len + 1);
    vector<int> order;
    order.reserve(len + 1);
    const auto dfs = fixed([&](auto&& dfs, const int u) -> void {
        if (done[u])
            return;
        done[u] = true;
        if (u >= M)
            dfs(u - M);
        if (u + N <= len)
            dfs(u + N);
        order.push_back(u);
    });
    for (int i = 0; i <= len; ++i) {
        dfs(i);
    }
    vector<int> rank(len + 1);
    for (int i = 0; i <= len; ++i) {
        rank[order[i]] = i;
    }
    vector<int> ret(len);
    for (int i = 0; i < len; ++i) {
        ret[i] = rank[i + 1] - rank[i];
    }
    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 276 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 316 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 320 KB Ok
11 Correct 1 ms 320 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 320 KB Ok
2 Correct 1 ms 320 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 324 KB Ok
5 Correct 2 ms 212 KB Ok
6 Correct 3 ms 380 KB Ok
7 Correct 9 ms 948 KB Ok
8 Correct 6 ms 572 KB Ok
9 Correct 10 ms 980 KB Ok
10 Correct 7 ms 660 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 316 KB Ok
4 Correct 3 ms 316 KB Ok
5 Correct 1 ms 316 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 316 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 212 KB Ok
3 Correct 1 ms 320 KB Ok
4 Correct 1 ms 320 KB Ok
5 Correct 1 ms 256 KB Ok
6 Correct 99 ms 6864 KB Ok
7 Correct 67 ms 10048 KB Ok
8 Correct 124 ms 13272 KB Ok
9 Correct 93 ms 12032 KB Ok
10 Correct 48 ms 5132 KB Ok
11 Correct 120 ms 9096 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 276 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 316 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 320 KB Ok
11 Correct 1 ms 320 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 320 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 316 KB Ok
16 Correct 3 ms 316 KB Ok
17 Correct 1 ms 316 KB Ok
18 Correct 1 ms 212 KB Ok
19 Correct 1 ms 212 KB Ok
20 Correct 1 ms 320 KB Ok
21 Correct 1 ms 212 KB Ok
22 Correct 1 ms 212 KB Ok
23 Correct 1 ms 316 KB Ok
24 Correct 2 ms 324 KB Ok
25 Correct 2 ms 340 KB Ok
26 Correct 4 ms 316 KB Ok
27 Correct 2 ms 320 KB Ok
28 Correct 2 ms 340 KB Ok
29 Correct 2 ms 320 KB Ok
30 Correct 3 ms 340 KB Ok
31 Correct 2 ms 316 KB Ok
32 Correct 3 ms 340 KB Ok
33 Correct 2 ms 340 KB Ok
34 Correct 4 ms 468 KB Ok
35 Correct 5 ms 596 KB Ok
36 Correct 4 ms 600 KB Ok
37 Correct 3 ms 500 KB Ok
38 Correct 4 ms 572 KB Ok
39 Correct 4 ms 448 KB Ok
40 Correct 9 ms 576 KB Ok
41 Correct 4 ms 576 KB Ok
42 Correct 5 ms 468 KB Ok
43 Correct 8 ms 596 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 276 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 316 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 320 KB Ok
11 Correct 1 ms 320 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 320 KB Ok
14 Correct 1 ms 320 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 324 KB Ok
17 Correct 2 ms 212 KB Ok
18 Correct 3 ms 380 KB Ok
19 Correct 9 ms 948 KB Ok
20 Correct 6 ms 572 KB Ok
21 Correct 10 ms 980 KB Ok
22 Correct 7 ms 660 KB Ok
23 Correct 1 ms 320 KB Ok
24 Correct 1 ms 212 KB Ok
25 Correct 1 ms 316 KB Ok
26 Correct 3 ms 316 KB Ok
27 Correct 1 ms 316 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 1 ms 212 KB Ok
30 Correct 1 ms 320 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 1 ms 316 KB Ok
34 Correct 2 ms 324 KB Ok
35 Correct 2 ms 340 KB Ok
36 Correct 4 ms 316 KB Ok
37 Correct 2 ms 320 KB Ok
38 Correct 2 ms 340 KB Ok
39 Correct 2 ms 320 KB Ok
40 Correct 3 ms 340 KB Ok
41 Correct 2 ms 316 KB Ok
42 Correct 3 ms 340 KB Ok
43 Correct 2 ms 340 KB Ok
44 Correct 4 ms 468 KB Ok
45 Correct 5 ms 596 KB Ok
46 Correct 4 ms 600 KB Ok
47 Correct 3 ms 500 KB Ok
48 Correct 4 ms 572 KB Ok
49 Correct 4 ms 448 KB Ok
50 Correct 9 ms 576 KB Ok
51 Correct 4 ms 576 KB Ok
52 Correct 5 ms 468 KB Ok
53 Correct 8 ms 596 KB Ok
54 Correct 70 ms 2976 KB Ok
55 Correct 78 ms 3348 KB Ok
56 Correct 76 ms 3216 KB Ok
57 Correct 60 ms 2368 KB Ok
58 Correct 63 ms 2628 KB Ok
59 Correct 62 ms 2564 KB Ok
60 Correct 56 ms 2392 KB Ok
61 Correct 59 ms 2456 KB Ok
62 Correct 70 ms 2832 KB Ok
63 Correct 57 ms 2556 KB Ok
64 Correct 83 ms 3192 KB Ok
65 Correct 71 ms 2984 KB Ok
66 Correct 81 ms 2800 KB Ok
67 Correct 52 ms 2716 KB Ok
68 Correct 51 ms 2608 KB Ok
69 Correct 100 ms 10440 KB Ok
70 Correct 96 ms 11104 KB Ok
71 Correct 99 ms 10572 KB Ok
72 Correct 114 ms 10452 KB Ok
73 Correct 93 ms 10140 KB Ok
74 Correct 101 ms 9884 KB Ok
75 Correct 105 ms 9780 KB Ok
76 Correct 133 ms 10784 KB Ok
77 Correct 106 ms 9484 KB Ok
78 Correct 116 ms 9780 KB Ok
79 Correct 132 ms 10448 KB Ok
80 Correct 115 ms 10556 KB Ok
81 Correct 99 ms 10096 KB Ok
82 Correct 110 ms 10364 KB Ok
83 Correct 129 ms 9848 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 276 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 316 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 320 KB Ok
11 Correct 1 ms 320 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 320 KB Ok
14 Correct 1 ms 320 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 324 KB Ok
17 Correct 2 ms 212 KB Ok
18 Correct 3 ms 380 KB Ok
19 Correct 9 ms 948 KB Ok
20 Correct 6 ms 572 KB Ok
21 Correct 10 ms 980 KB Ok
22 Correct 7 ms 660 KB Ok
23 Correct 1 ms 320 KB Ok
24 Correct 1 ms 212 KB Ok
25 Correct 1 ms 316 KB Ok
26 Correct 3 ms 316 KB Ok
27 Correct 1 ms 316 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 1 ms 212 KB Ok
30 Correct 1 ms 320 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 1 ms 316 KB Ok
34 Correct 1 ms 212 KB Ok
35 Correct 1 ms 212 KB Ok
36 Correct 1 ms 320 KB Ok
37 Correct 1 ms 320 KB Ok
38 Correct 1 ms 256 KB Ok
39 Correct 99 ms 6864 KB Ok
40 Correct 67 ms 10048 KB Ok
41 Correct 124 ms 13272 KB Ok
42 Correct 93 ms 12032 KB Ok
43 Correct 48 ms 5132 KB Ok
44 Correct 120 ms 9096 KB Ok
45 Correct 2 ms 324 KB Ok
46 Correct 2 ms 340 KB Ok
47 Correct 4 ms 316 KB Ok
48 Correct 2 ms 320 KB Ok
49 Correct 2 ms 340 KB Ok
50 Correct 2 ms 320 KB Ok
51 Correct 3 ms 340 KB Ok
52 Correct 2 ms 316 KB Ok
53 Correct 3 ms 340 KB Ok
54 Correct 2 ms 340 KB Ok
55 Correct 4 ms 468 KB Ok
56 Correct 5 ms 596 KB Ok
57 Correct 4 ms 600 KB Ok
58 Correct 3 ms 500 KB Ok
59 Correct 4 ms 572 KB Ok
60 Correct 4 ms 448 KB Ok
61 Correct 9 ms 576 KB Ok
62 Correct 4 ms 576 KB Ok
63 Correct 5 ms 468 KB Ok
64 Correct 8 ms 596 KB Ok
65 Correct 70 ms 2976 KB Ok
66 Correct 78 ms 3348 KB Ok
67 Correct 76 ms 3216 KB Ok
68 Correct 60 ms 2368 KB Ok
69 Correct 63 ms 2628 KB Ok
70 Correct 62 ms 2564 KB Ok
71 Correct 56 ms 2392 KB Ok
72 Correct 59 ms 2456 KB Ok
73 Correct 70 ms 2832 KB Ok
74 Correct 57 ms 2556 KB Ok
75 Correct 83 ms 3192 KB Ok
76 Correct 71 ms 2984 KB Ok
77 Correct 81 ms 2800 KB Ok
78 Correct 52 ms 2716 KB Ok
79 Correct 51 ms 2608 KB Ok
80 Correct 100 ms 10440 KB Ok
81 Correct 96 ms 11104 KB Ok
82 Correct 99 ms 10572 KB Ok
83 Correct 114 ms 10452 KB Ok
84 Correct 93 ms 10140 KB Ok
85 Correct 101 ms 9884 KB Ok
86 Correct 105 ms 9780 KB Ok
87 Correct 133 ms 10784 KB Ok
88 Correct 106 ms 9484 KB Ok
89 Correct 116 ms 9780 KB Ok
90 Correct 132 ms 10448 KB Ok
91 Correct 115 ms 10556 KB Ok
92 Correct 99 ms 10096 KB Ok
93 Correct 110 ms 10364 KB Ok
94 Correct 129 ms 9848 KB Ok
95 Correct 155 ms 7040 KB Ok
96 Correct 244 ms 9404 KB Ok
97 Correct 229 ms 8156 KB Ok
98 Correct 159 ms 6328 KB Ok
99 Correct 184 ms 7984 KB Ok
100 Correct 165 ms 7860 KB Ok
101 Correct 183 ms 8500 KB Ok
102 Correct 171 ms 8740 KB Ok
103 Correct 195 ms 8008 KB Ok
104 Correct 202 ms 9372 KB Ok
105 Correct 199 ms 9388 KB Ok
106 Correct 170 ms 8524 KB Ok
107 Correct 196 ms 9192 KB Ok
108 Correct 210 ms 9736 KB Ok
109 Correct 192 ms 8860 KB Ok
110 Correct 415 ms 42004 KB Ok
111 Correct 420 ms 44264 KB Ok
112 Correct 458 ms 41696 KB Ok
113 Correct 390 ms 44500 KB Ok
114 Correct 460 ms 44660 KB Ok
115 Correct 380 ms 42100 KB Ok
116 Correct 382 ms 44452 KB Ok
117 Correct 378 ms 43576 KB Ok
118 Correct 398 ms 43968 KB Ok
119 Correct 370 ms 40648 KB Ok
120 Correct 373 ms 42968 KB Ok
121 Correct 370 ms 42572 KB Ok
122 Correct 381 ms 43116 KB Ok
123 Correct 396 ms 44676 KB Ok
124 Correct 389 ms 39484 KB Ok
125 Correct 354 ms 27956 KB Ok