oj.uz

Submission #873885

# Submission time Handle Problem Language Result Execution time Memory
873885 2023-11-16T02:30:29 Z noiaint Nice sequence (IZhO18_sequence) C++17
100 / 100
 323 ms 47604 KB 
#include <bits/stdc++.h>

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, m;
int len;
int timer = 0;
int vis[N], a[N];

void dfs(int u) {
	if (u < 0 || u > len || vis[u])
		return;
	vis[u] = true;
	dfs(u - n);
	dfs(u + m);
	a[u] = timer++;
}

void solve() {
	cin >> n >> m;
	len = n + m - 1 - __gcd(m, n);
	timer = 0;
	memset(vis, 0, sizeof vis);

	for (int i = 0; i <= len; ++i)
		dfs(i);
	cout << len << '\n';
	for (int i = 0; i < len; ++i) {
		cout << a[i] - a[i + 1] << ' ';
	}
	cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    int q;
    cin >> q;
    while (q--) {
    	solve();
    }

    return 0;
}

/*

*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5976 KB Ok
2 Correct 2 ms 5976 KB Ok
3 Correct 3 ms 5980 KB Ok
4 Correct 3 ms 5976 KB Ok
5 Correct 3 ms 5980 KB Ok
6 Correct 3 ms 5980 KB Ok
7 Correct 3 ms 5980 KB Ok
8 Correct 3 ms 5980 KB Ok
9 Correct 2 ms 5976 KB Ok
10 Correct 2 ms 5984 KB Ok
11 Correct 3 ms 5980 KB Ok
12 Correct 2 ms 5980 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5980 KB Ok
2 Correct 3 ms 5976 KB Ok
3 Correct 3 ms 5980 KB Ok
4 Correct 2 ms 5848 KB Ok
5 Correct 3 ms 5980 KB Ok
6 Correct 4 ms 5976 KB Ok
7 Correct 12 ms 6492 KB Ok
8 Correct 5 ms 6232 KB Ok
9 Correct 8 ms 6748 KB Ok
10 Correct 6 ms 6232 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Ok
2 Correct 2 ms 6176 KB Ok
3 Correct 2 ms 5980 KB Ok
4 Correct 2 ms 5976 KB Ok
5 Correct 3 ms 5980 KB Ok
6 Correct 2 ms 5980 KB Ok
7 Correct 3 ms 5980 KB Ok
8 Correct 3 ms 5976 KB Ok
9 Correct 2 ms 5980 KB Ok
10 Correct 2 ms 5980 KB Ok
11 Correct 2 ms 5980 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5976 KB Ok
2 Correct 2 ms 5980 KB Ok
3 Correct 2 ms 5980 KB Ok
4 Correct 2 ms 5844 KB Ok
5 Correct 2 ms 5980 KB Ok
6 Correct 52 ms 16472 KB Ok
7 Correct 44 ms 14904 KB Ok
8 Correct 84 ms 18000 KB Ok
9 Correct 67 ms 16468 KB Ok
10 Correct 40 ms 13652 KB Ok
11 Correct 103 ms 19228 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5976 KB Ok
2 Correct 2 ms 5976 KB Ok
3 Correct 3 ms 5980 KB Ok
4 Correct 3 ms 5976 KB Ok
5 Correct 3 ms 5980 KB Ok
6 Correct 3 ms 5980 KB Ok
7 Correct 3 ms 5980 KB Ok
8 Correct 3 ms 5980 KB Ok
9 Correct 2 ms 5976 KB Ok
10 Correct 2 ms 5984 KB Ok
11 Correct 3 ms 5980 KB Ok
12 Correct 2 ms 5980 KB Ok
13 Correct 2 ms 5980 KB Ok
14 Correct 2 ms 6176 KB Ok
15 Correct 2 ms 5980 KB Ok
16 Correct 2 ms 5976 KB Ok
17 Correct 3 ms 5980 KB Ok
18 Correct 2 ms 5980 KB Ok
19 Correct 3 ms 5980 KB Ok
20 Correct 3 ms 5976 KB Ok
21 Correct 2 ms 5980 KB Ok
22 Correct 2 ms 5980 KB Ok
23 Correct 2 ms 5980 KB Ok
24 Correct 4 ms 5976 KB Ok
25 Correct 3 ms 5976 KB Ok
26 Correct 3 ms 5976 KB Ok
27 Correct 4 ms 5980 KB Ok
28 Correct 3 ms 5976 KB Ok
29 Correct 3 ms 5976 KB Ok
30 Correct 3 ms 5976 KB Ok
31 Correct 4 ms 5980 KB Ok
32 Correct 3 ms 5976 KB Ok
33 Correct 4 ms 5980 KB Ok
34 Correct 5 ms 6092 KB Ok
35 Correct 4 ms 6128 KB Ok
36 Correct 5 ms 6236 KB Ok
37 Correct 4 ms 6236 KB Ok
38 Correct 4 ms 6236 KB Ok
39 Correct 4 ms 6232 KB Ok
40 Correct 5 ms 6236 KB Ok
41 Correct 4 ms 6236 KB Ok
42 Correct 5 ms 6236 KB Ok
43 Correct 5 ms 6236 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5976 KB Ok
2 Correct 2 ms 5976 KB Ok
3 Correct 3 ms 5980 KB Ok
4 Correct 3 ms 5976 KB Ok
5 Correct 3 ms 5980 KB Ok
6 Correct 3 ms 5980 KB Ok
7 Correct 3 ms 5980 KB Ok
8 Correct 3 ms 5980 KB Ok
9 Correct 2 ms 5976 KB Ok
10 Correct 2 ms 5984 KB Ok
11 Correct 3 ms 5980 KB Ok
12 Correct 2 ms 5980 KB Ok
13 Correct 3 ms 5980 KB Ok
14 Correct 3 ms 5976 KB Ok
15 Correct 3 ms 5980 KB Ok
16 Correct 2 ms 5848 KB Ok
17 Correct 3 ms 5980 KB Ok
18 Correct 4 ms 5976 KB Ok
19 Correct 12 ms 6492 KB Ok
20 Correct 5 ms 6232 KB Ok
21 Correct 8 ms 6748 KB Ok
22 Correct 6 ms 6232 KB Ok
23 Correct 2 ms 5980 KB Ok
24 Correct 2 ms 6176 KB Ok
25 Correct 2 ms 5980 KB Ok
26 Correct 2 ms 5976 KB Ok
27 Correct 3 ms 5980 KB Ok
28 Correct 2 ms 5980 KB Ok
29 Correct 3 ms 5980 KB Ok
30 Correct 3 ms 5976 KB Ok
31 Correct 2 ms 5980 KB Ok
32 Correct 2 ms 5980 KB Ok
33 Correct 2 ms 5980 KB Ok
34 Correct 4 ms 5976 KB Ok
35 Correct 3 ms 5976 KB Ok
36 Correct 3 ms 5976 KB Ok
37 Correct 4 ms 5980 KB Ok
38 Correct 3 ms 5976 KB Ok
39 Correct 3 ms 5976 KB Ok
40 Correct 3 ms 5976 KB Ok
41 Correct 4 ms 5980 KB Ok
42 Correct 3 ms 5976 KB Ok
43 Correct 4 ms 5980 KB Ok
44 Correct 5 ms 6092 KB Ok
45 Correct 4 ms 6128 KB Ok
46 Correct 5 ms 6236 KB Ok
47 Correct 4 ms 6236 KB Ok
48 Correct 4 ms 6236 KB Ok
49 Correct 4 ms 6232 KB Ok
50 Correct 5 ms 6236 KB Ok
51 Correct 4 ms 6236 KB Ok
52 Correct 5 ms 6236 KB Ok
53 Correct 5 ms 6236 KB Ok
54 Correct 44 ms 10432 KB Ok
55 Correct 76 ms 10832 KB Ok
56 Correct 51 ms 10560 KB Ok
57 Correct 35 ms 10016 KB Ok
58 Correct 70 ms 10488 KB Ok
59 Correct 39 ms 10588 KB Ok
60 Correct 46 ms 10064 KB Ok
61 Correct 40 ms 10536 KB Ok
62 Correct 46 ms 10836 KB Ok
63 Correct 64 ms 10320 KB Ok
64 Correct 69 ms 10832 KB Ok
65 Correct 43 ms 10540 KB Ok
66 Correct 38 ms 10324 KB Ok
67 Correct 36 ms 10064 KB Ok
68 Correct 65 ms 10324 KB Ok
69 Correct 75 ms 17264 KB Ok
70 Correct 73 ms 17380 KB Ok
71 Correct 65 ms 15884 KB Ok
72 Correct 69 ms 17168 KB Ok
73 Correct 90 ms 16208 KB Ok
74 Correct 64 ms 16676 KB Ok
75 Correct 69 ms 16980 KB Ok
76 Correct 70 ms 17276 KB Ok
77 Correct 68 ms 16336 KB Ok
78 Correct 83 ms 17236 KB Ok
79 Correct 72 ms 16724 KB Ok
80 Correct 84 ms 15904 KB Ok
81 Correct 78 ms 17392 KB Ok
82 Correct 83 ms 16704 KB Ok
83 Correct 68 ms 17464 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5976 KB Ok
2 Correct 2 ms 5976 KB Ok
3 Correct 3 ms 5980 KB Ok
4 Correct 3 ms 5976 KB Ok
5 Correct 3 ms 5980 KB Ok
6 Correct 3 ms 5980 KB Ok
7 Correct 3 ms 5980 KB Ok
8 Correct 3 ms 5980 KB Ok
9 Correct 2 ms 5976 KB Ok
10 Correct 2 ms 5984 KB Ok
11 Correct 3 ms 5980 KB Ok
12 Correct 2 ms 5980 KB Ok
13 Correct 3 ms 5980 KB Ok
14 Correct 3 ms 5976 KB Ok
15 Correct 3 ms 5980 KB Ok
16 Correct 2 ms 5848 KB Ok
17 Correct 3 ms 5980 KB Ok
18 Correct 4 ms 5976 KB Ok
19 Correct 12 ms 6492 KB Ok
20 Correct 5 ms 6232 KB Ok
21 Correct 8 ms 6748 KB Ok
22 Correct 6 ms 6232 KB Ok
23 Correct 2 ms 5980 KB Ok
24 Correct 2 ms 6176 KB Ok
25 Correct 2 ms 5980 KB Ok
26 Correct 2 ms 5976 KB Ok
27 Correct 3 ms 5980 KB Ok
28 Correct 2 ms 5980 KB Ok
29 Correct 3 ms 5980 KB Ok
30 Correct 3 ms 5976 KB Ok
31 Correct 2 ms 5980 KB Ok
32 Correct 2 ms 5980 KB Ok
33 Correct 2 ms 5980 KB Ok
34 Correct 3 ms 5976 KB Ok
35 Correct 2 ms 5980 KB Ok
36 Correct 2 ms 5980 KB Ok
37 Correct 2 ms 5844 KB Ok
38 Correct 2 ms 5980 KB Ok
39 Correct 52 ms 16472 KB Ok
40 Correct 44 ms 14904 KB Ok
41 Correct 84 ms 18000 KB Ok
42 Correct 67 ms 16468 KB Ok
43 Correct 40 ms 13652 KB Ok
44 Correct 103 ms 19228 KB Ok
45 Correct 4 ms 5976 KB Ok
46 Correct 3 ms 5976 KB Ok
47 Correct 3 ms 5976 KB Ok
48 Correct 4 ms 5980 KB Ok
49 Correct 3 ms 5976 KB Ok
50 Correct 3 ms 5976 KB Ok
51 Correct 3 ms 5976 KB Ok
52 Correct 4 ms 5980 KB Ok
53 Correct 3 ms 5976 KB Ok
54 Correct 4 ms 5980 KB Ok
55 Correct 5 ms 6092 KB Ok
56 Correct 4 ms 6128 KB Ok
57 Correct 5 ms 6236 KB Ok
58 Correct 4 ms 6236 KB Ok
59 Correct 4 ms 6236 KB Ok
60 Correct 4 ms 6232 KB Ok
61 Correct 5 ms 6236 KB Ok
62 Correct 4 ms 6236 KB Ok
63 Correct 5 ms 6236 KB Ok
64 Correct 5 ms 6236 KB Ok
65 Correct 44 ms 10432 KB Ok
66 Correct 76 ms 10832 KB Ok
67 Correct 51 ms 10560 KB Ok
68 Correct 35 ms 10016 KB Ok
69 Correct 70 ms 10488 KB Ok
70 Correct 39 ms 10588 KB Ok
71 Correct 46 ms 10064 KB Ok
72 Correct 40 ms 10536 KB Ok
73 Correct 46 ms 10836 KB Ok
74 Correct 64 ms 10320 KB Ok
75 Correct 69 ms 10832 KB Ok
76 Correct 43 ms 10540 KB Ok
77 Correct 38 ms 10324 KB Ok
78 Correct 36 ms 10064 KB Ok
79 Correct 65 ms 10324 KB Ok
80 Correct 75 ms 17264 KB Ok
81 Correct 73 ms 17380 KB Ok
82 Correct 65 ms 15884 KB Ok
83 Correct 69 ms 17168 KB Ok
84 Correct 90 ms 16208 KB Ok
85 Correct 64 ms 16676 KB Ok
86 Correct 69 ms 16980 KB Ok
87 Correct 70 ms 17276 KB Ok
88 Correct 68 ms 16336 KB Ok
89 Correct 83 ms 17236 KB Ok
90 Correct 72 ms 16724 KB Ok
91 Correct 84 ms 15904 KB Ok
92 Correct 78 ms 17392 KB Ok
93 Correct 83 ms 16704 KB Ok
94 Correct 68 ms 17464 KB Ok
95 Correct 117 ms 13916 KB Ok
96 Correct 146 ms 16724 KB Ok
97 Correct 129 ms 15908 KB Ok
98 Correct 116 ms 14072 KB Ok
99 Correct 115 ms 14776 KB Ok
100 Correct 118 ms 15952 KB Ok
101 Correct 124 ms 15188 KB Ok
102 Correct 173 ms 15428 KB Ok
103 Correct 140 ms 15644 KB Ok
104 Correct 146 ms 16540 KB Ok
105 Correct 126 ms 16468 KB Ok
106 Correct 114 ms 14736 KB Ok
107 Correct 128 ms 15816 KB Ok
108 Correct 162 ms 17076 KB Ok
109 Correct 138 ms 15836 KB Ok
110 Correct 282 ms 46748 KB Ok
111 Correct 312 ms 47604 KB Ok
112 Correct 275 ms 43340 KB Ok
113 Correct 290 ms 46716 KB Ok
114 Correct 284 ms 42644 KB Ok
115 Correct 312 ms 47532 KB Ok
116 Correct 291 ms 47204 KB Ok
117 Correct 323 ms 47368 KB Ok
118 Correct 302 ms 41800 KB Ok
119 Correct 291 ms 46528 KB Ok
120 Correct 314 ms 46792 KB Ok
121 Correct 280 ms 44436 KB Ok
122 Correct 304 ms 47456 KB Ok
123 Correct 274 ms 45392 KB Ok
124 Correct 291 ms 43020 KB Ok
125 Correct 240 ms 30632 KB Ok