oj.uz

Submission #946056

# Submission time Handle Problem Language Result Execution time Memory
946056 2024-03-14T09:53:21 Z atom Nice sequence (IZhO18_sequence) C++17
100 / 100
 1100 ms 53980 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 2e5 + 5;
int n, m;
vector <int> adj[N << 1];
int deg[N << 1], a[N << 1];

bool check(int k) {
    for (int i = 0; i <= k; ++i) {
        if (i + m <= k) {
            adj[i].push_back(i + m);
            deg[i + m]++;
        }
        if (i >= n) {
            adj[i].push_back(i - n);
            deg[i - n]++;
        }
    }

    queue <int> q;
    for (int i = 0; i <= k; ++i)
        if (deg[i] == 0)
            q.push(i);

    int cnt = 0;
    vector <int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        a[u] = ++cnt;
        for (int v : adj[u]) {
            deg[v]--;
            if (deg[v] == 0) q.push(v);
        }
    }
    for (int i = 0; i <= k; ++i) {
        adj[i].clear();
        deg[i] = 0;
    }
    // if the graph is cyclic then no topo order exists
    return ((int) topo.size() == k + 1);
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int T; 
    cin >> T;
    while (T--) {
        cin >> n >> m;
        int ans = (n + m - 1 - __gcd(n, m));
        check(ans);
        cout << ans << "\n";
        for (int i = 1; i <= ans; ++i) {
            cout << (a[i] - a[i - 1]) << " \n"[i == ans];
        }   
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Ok
2 Correct 3 ms 12636 KB Ok
3 Correct 4 ms 10584 KB Ok
4 Correct 3 ms 10588 KB Ok
5 Correct 3 ms 12632 KB Ok
6 Correct 2 ms 10588 KB Ok
7 Correct 3 ms 10588 KB Ok
8 Correct 3 ms 12632 KB Ok
9 Correct 2 ms 10756 KB Ok
10 Correct 2 ms 10588 KB Ok
11 Correct 2 ms 10768 KB Ok
12 Correct 2 ms 10588 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10756 KB Ok
2 Correct 2 ms 12636 KB Ok
3 Correct 2 ms 12636 KB Ok
4 Correct 2 ms 12632 KB Ok
5 Correct 3 ms 12636 KB Ok
6 Correct 4 ms 12892 KB Ok
7 Correct 11 ms 13404 KB Ok
8 Correct 7 ms 12892 KB Ok
9 Correct 13 ms 13460 KB Ok
10 Correct 6 ms 13148 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Ok
2 Correct 2 ms 12636 KB Ok
3 Correct 2 ms 12636 KB Ok
4 Correct 3 ms 12632 KB Ok
5 Correct 3 ms 12636 KB Ok
6 Correct 2 ms 10588 KB Ok
7 Correct 2 ms 12636 KB Ok
8 Correct 2 ms 12636 KB Ok
9 Correct 2 ms 12636 KB Ok
10 Correct 3 ms 12636 KB Ok
11 Correct 3 ms 12636 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Ok
2 Correct 3 ms 12636 KB Ok
3 Correct 3 ms 12636 KB Ok
4 Correct 3 ms 12636 KB Ok
5 Correct 3 ms 12636 KB Ok
6 Correct 61 ms 21788 KB Ok
7 Correct 54 ms 21972 KB Ok
8 Correct 96 ms 24368 KB Ok
9 Correct 75 ms 24036 KB Ok
10 Correct 44 ms 18884 KB Ok
11 Correct 73 ms 23012 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Ok
2 Correct 3 ms 12636 KB Ok
3 Correct 4 ms 10584 KB Ok
4 Correct 3 ms 10588 KB Ok
5 Correct 3 ms 12632 KB Ok
6 Correct 2 ms 10588 KB Ok
7 Correct 3 ms 10588 KB Ok
8 Correct 3 ms 12632 KB Ok
9 Correct 2 ms 10756 KB Ok
10 Correct 2 ms 10588 KB Ok
11 Correct 2 ms 10768 KB Ok
12 Correct 2 ms 10588 KB Ok
13 Correct 2 ms 12632 KB Ok
14 Correct 2 ms 12636 KB Ok
15 Correct 2 ms 12636 KB Ok
16 Correct 3 ms 12632 KB Ok
17 Correct 3 ms 12636 KB Ok
18 Correct 2 ms 10588 KB Ok
19 Correct 2 ms 12636 KB Ok
20 Correct 2 ms 12636 KB Ok
21 Correct 2 ms 12636 KB Ok
22 Correct 3 ms 12636 KB Ok
23 Correct 3 ms 12636 KB Ok
24 Correct 3 ms 12892 KB Ok
25 Correct 4 ms 12888 KB Ok
26 Correct 4 ms 12892 KB Ok
27 Correct 3 ms 10844 KB Ok
28 Correct 3 ms 10844 KB Ok
29 Correct 5 ms 10844 KB Ok
30 Correct 3 ms 12892 KB Ok
31 Correct 3 ms 10840 KB Ok
32 Correct 3 ms 12892 KB Ok
33 Correct 4 ms 12984 KB Ok
34 Correct 5 ms 12892 KB Ok
35 Correct 6 ms 12892 KB Ok
36 Correct 5 ms 12892 KB Ok
37 Correct 5 ms 12892 KB Ok
38 Correct 7 ms 12888 KB Ok
39 Correct 5 ms 12892 KB Ok
40 Correct 6 ms 12888 KB Ok
41 Correct 5 ms 12892 KB Ok
42 Correct 5 ms 12892 KB Ok
43 Correct 5 ms 12888 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Ok
2 Correct 3 ms 12636 KB Ok
3 Correct 4 ms 10584 KB Ok
4 Correct 3 ms 10588 KB Ok
5 Correct 3 ms 12632 KB Ok
6 Correct 2 ms 10588 KB Ok
7 Correct 3 ms 10588 KB Ok
8 Correct 3 ms 12632 KB Ok
9 Correct 2 ms 10756 KB Ok
10 Correct 2 ms 10588 KB Ok
11 Correct 2 ms 10768 KB Ok
12 Correct 2 ms 10588 KB Ok
13 Correct 2 ms 10756 KB Ok
14 Correct 2 ms 12636 KB Ok
15 Correct 2 ms 12636 KB Ok
16 Correct 2 ms 12632 KB Ok
17 Correct 3 ms 12636 KB Ok
18 Correct 4 ms 12892 KB Ok
19 Correct 11 ms 13404 KB Ok
20 Correct 7 ms 12892 KB Ok
21 Correct 13 ms 13460 KB Ok
22 Correct 6 ms 13148 KB Ok
23 Correct 2 ms 12632 KB Ok
24 Correct 2 ms 12636 KB Ok
25 Correct 2 ms 12636 KB Ok
26 Correct 3 ms 12632 KB Ok
27 Correct 3 ms 12636 KB Ok
28 Correct 2 ms 10588 KB Ok
29 Correct 2 ms 12636 KB Ok
30 Correct 2 ms 12636 KB Ok
31 Correct 2 ms 12636 KB Ok
32 Correct 3 ms 12636 KB Ok
33 Correct 3 ms 12636 KB Ok
34 Correct 3 ms 12892 KB Ok
35 Correct 4 ms 12888 KB Ok
36 Correct 4 ms 12892 KB Ok
37 Correct 3 ms 10844 KB Ok
38 Correct 3 ms 10844 KB Ok
39 Correct 5 ms 10844 KB Ok
40 Correct 3 ms 12892 KB Ok
41 Correct 3 ms 10840 KB Ok
42 Correct 3 ms 12892 KB Ok
43 Correct 4 ms 12984 KB Ok
44 Correct 5 ms 12892 KB Ok
45 Correct 6 ms 12892 KB Ok
46 Correct 5 ms 12892 KB Ok
47 Correct 5 ms 12892 KB Ok
48 Correct 7 ms 12888 KB Ok
49 Correct 5 ms 12892 KB Ok
50 Correct 6 ms 12888 KB Ok
51 Correct 5 ms 12892 KB Ok
52 Correct 5 ms 12892 KB Ok
53 Correct 5 ms 12888 KB Ok
54 Correct 43 ms 17892 KB Ok
55 Correct 49 ms 17968 KB Ok
56 Correct 55 ms 16584 KB Ok
57 Correct 38 ms 15864 KB Ok
58 Correct 47 ms 16260 KB Ok
59 Correct 45 ms 17656 KB Ok
60 Correct 38 ms 17512 KB Ok
61 Correct 39 ms 16148 KB Ok
62 Correct 53 ms 17948 KB Ok
63 Correct 43 ms 15996 KB Ok
64 Correct 48 ms 16372 KB Ok
65 Correct 61 ms 18172 KB Ok
66 Correct 52 ms 16196 KB Ok
67 Correct 37 ms 15900 KB Ok
68 Correct 42 ms 17808 KB Ok
69 Correct 94 ms 21764 KB Ok
70 Correct 138 ms 22760 KB Ok
71 Correct 90 ms 21104 KB Ok
72 Correct 108 ms 21836 KB Ok
73 Correct 90 ms 21716 KB Ok
74 Correct 81 ms 20740 KB Ok
75 Correct 93 ms 20412 KB Ok
76 Correct 155 ms 22560 KB Ok
77 Correct 77 ms 20340 KB Ok
78 Correct 104 ms 22264 KB Ok
79 Correct 95 ms 21736 KB Ok
80 Correct 94 ms 21732 KB Ok
81 Correct 98 ms 21924 KB Ok
82 Correct 122 ms 21508 KB Ok
83 Correct 93 ms 20728 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Ok
2 Correct 3 ms 12636 KB Ok
3 Correct 4 ms 10584 KB Ok
4 Correct 3 ms 10588 KB Ok
5 Correct 3 ms 12632 KB Ok
6 Correct 2 ms 10588 KB Ok
7 Correct 3 ms 10588 KB Ok
8 Correct 3 ms 12632 KB Ok
9 Correct 2 ms 10756 KB Ok
10 Correct 2 ms 10588 KB Ok
11 Correct 2 ms 10768 KB Ok
12 Correct 2 ms 10588 KB Ok
13 Correct 2 ms 10756 KB Ok
14 Correct 2 ms 12636 KB Ok
15 Correct 2 ms 12636 KB Ok
16 Correct 2 ms 12632 KB Ok
17 Correct 3 ms 12636 KB Ok
18 Correct 4 ms 12892 KB Ok
19 Correct 11 ms 13404 KB Ok
20 Correct 7 ms 12892 KB Ok
21 Correct 13 ms 13460 KB Ok
22 Correct 6 ms 13148 KB Ok
23 Correct 2 ms 12632 KB Ok
24 Correct 2 ms 12636 KB Ok
25 Correct 2 ms 12636 KB Ok
26 Correct 3 ms 12632 KB Ok
27 Correct 3 ms 12636 KB Ok
28 Correct 2 ms 10588 KB Ok
29 Correct 2 ms 12636 KB Ok
30 Correct 2 ms 12636 KB Ok
31 Correct 2 ms 12636 KB Ok
32 Correct 3 ms 12636 KB Ok
33 Correct 3 ms 12636 KB Ok
34 Correct 3 ms 12632 KB Ok
35 Correct 3 ms 12636 KB Ok
36 Correct 3 ms 12636 KB Ok
37 Correct 3 ms 12636 KB Ok
38 Correct 3 ms 12636 KB Ok
39 Correct 61 ms 21788 KB Ok
40 Correct 54 ms 21972 KB Ok
41 Correct 96 ms 24368 KB Ok
42 Correct 75 ms 24036 KB Ok
43 Correct 44 ms 18884 KB Ok
44 Correct 73 ms 23012 KB Ok
45 Correct 3 ms 12892 KB Ok
46 Correct 4 ms 12888 KB Ok
47 Correct 4 ms 12892 KB Ok
48 Correct 3 ms 10844 KB Ok
49 Correct 3 ms 10844 KB Ok
50 Correct 5 ms 10844 KB Ok
51 Correct 3 ms 12892 KB Ok
52 Correct 3 ms 10840 KB Ok
53 Correct 3 ms 12892 KB Ok
54 Correct 4 ms 12984 KB Ok
55 Correct 5 ms 12892 KB Ok
56 Correct 6 ms 12892 KB Ok
57 Correct 5 ms 12892 KB Ok
58 Correct 5 ms 12892 KB Ok
59 Correct 7 ms 12888 KB Ok
60 Correct 5 ms 12892 KB Ok
61 Correct 6 ms 12888 KB Ok
62 Correct 5 ms 12892 KB Ok
63 Correct 5 ms 12892 KB Ok
64 Correct 5 ms 12888 KB Ok
65 Correct 43 ms 17892 KB Ok
66 Correct 49 ms 17968 KB Ok
67 Correct 55 ms 16584 KB Ok
68 Correct 38 ms 15864 KB Ok
69 Correct 47 ms 16260 KB Ok
70 Correct 45 ms 17656 KB Ok
71 Correct 38 ms 17512 KB Ok
72 Correct 39 ms 16148 KB Ok
73 Correct 53 ms 17948 KB Ok
74 Correct 43 ms 15996 KB Ok
75 Correct 48 ms 16372 KB Ok
76 Correct 61 ms 18172 KB Ok
77 Correct 52 ms 16196 KB Ok
78 Correct 37 ms 15900 KB Ok
79 Correct 42 ms 17808 KB Ok
80 Correct 94 ms 21764 KB Ok
81 Correct 138 ms 22760 KB Ok
82 Correct 90 ms 21104 KB Ok
83 Correct 108 ms 21836 KB Ok
84 Correct 90 ms 21716 KB Ok
85 Correct 81 ms 20740 KB Ok
86 Correct 93 ms 20412 KB Ok
87 Correct 155 ms 22560 KB Ok
88 Correct 77 ms 20340 KB Ok
89 Correct 104 ms 22264 KB Ok
90 Correct 95 ms 21736 KB Ok
91 Correct 94 ms 21732 KB Ok
92 Correct 98 ms 21924 KB Ok
93 Correct 122 ms 21508 KB Ok
94 Correct 93 ms 20728 KB Ok
95 Correct 105 ms 25100 KB Ok
96 Correct 209 ms 31280 KB Ok
97 Correct 152 ms 28832 KB Ok
98 Correct 119 ms 28652 KB Ok
99 Correct 137 ms 28276 KB Ok
100 Correct 136 ms 27700 KB Ok
101 Correct 149 ms 30604 KB Ok
102 Correct 136 ms 29796 KB Ok
103 Correct 135 ms 29264 KB Ok
104 Correct 162 ms 30780 KB Ok
105 Correct 151 ms 31368 KB Ok
106 Correct 126 ms 30868 KB Ok
107 Correct 156 ms 30048 KB Ok
108 Correct 155 ms 31280 KB Ok
109 Correct 144 ms 31592 KB Ok
110 Correct 646 ms 45336 KB Ok
111 Correct 1020 ms 53928 KB Ok
112 Correct 845 ms 47960 KB Ok
113 Correct 968 ms 50056 KB Ok
114 Correct 913 ms 52864 KB Ok
115 Correct 1071 ms 51276 KB Ok
116 Correct 939 ms 52356 KB Ok
117 Correct 946 ms 52072 KB Ok
118 Correct 811 ms 46972 KB Ok
119 Correct 883 ms 53056 KB Ok
120 Correct 812 ms 47340 KB Ok
121 Correct 776 ms 48344 KB Ok
122 Correct 772 ms 49380 KB Ok
123 Correct 1100 ms 53980 KB Ok
124 Correct 600 ms 44780 KB Ok
125 Correct 271 ms 38268 KB Ok