//#pragma GCC target ("avx2,sse2")
//#pragma GCC optimization ("Ofast")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
//#define endl "\n"
#define left fsdkfsdfsdfd
#define sum dfsdfsdfsdf
#define assign sdkfskdfkk
//#define int long long
using namespace std;
void dout() {
cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
cerr << H << ' ';
dout(T...);
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
int bit(signed x) {
return __builtin_popcount(x);
}
int bit(ll x) {
return __builtin_popcountll(x);
}
const int N = 4e5 + 123;
int n, m, k, used[N], p[N], a[N];
bool cycle;
vector <int> topsort;
void cleanup() {
cycle = false;
topsort = {};
for (int i = 0; i <= k; i++) {
used[i] = p[i] = a[i] = 0;
}
k = 0;
}
void dfs(int v) {
used[v] = 1;
if (v - n >= 0) {
if (used[v - n] == 1) {
cycle = true;
return;
}
if (used[v - n] == 0) {
dfs(v - n);
}
}
if (v + m <= k) {
if (used[v + m] == 1) {
cycle = true;
return;
}
if (used[v + m] == 0) {
dfs(v + m);
}
}
used[v] = 2;
}
void get(int v) {
used[v] = 1;
if (v - n >= 0) {
if (!used[v - n]) {
get(v - n);
}
}
if (v + m <= k) {
if (!used[v + m]) {
get(v + m);
}
}
topsort.pb(v);
}
bool check() {
if (k == 0) {
return true;
}
cycle = false;
for (int i = 0; i <= k; i++) {
if (used[i] == 0) {
dfs(i);
}
}
for (int i = 0; i <= k; i++) {
used[i] = 0;
}
return !cycle;
}
void construct() {
for (int i = 0; i <= k; i++) {
if (used[i] == 0) {
get(i);
}
}
reverse(topsort.begin(), topsort.end());
for (int i = 0; i <= k; i++) {
p[topsort[i]] = i;
}
bool zero = false;
for (int i = 1; i <= k; i++) {
a[i] = p[i] - p[i - 1];
if (a[i] == 0) {
zero = true;
}
}
cout << k << endl;
for (int i = 1; i <= k; i++) {
if (zero) {
a[i]++;
}
cout << a[i] << " ";
}
cout << endl;
}
void solve(int tc) {
// check for (int i = 0; i < n; j++)
cin >> n >> m;
int l = min(n, m) - 2, r = 2 * max(n, m) + 7;
while (l < r - 1) {
int mid = l + r >> 1;
k = mid;
if (check()) {
l = mid;
} else {
r = mid;
}
}
k = l;
construct();
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc = 1;
cin >> tc;
for (int i = 0; i < tc; i++) {
solve(i);
cleanup();
}
}
Compilation message
sequence.cpp: In function 'void solve(int)':
sequence.cpp:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Ok |
2 |
Correct |
2 ms |
376 KB |
Ok |
3 |
Correct |
2 ms |
376 KB |
Ok |
4 |
Correct |
2 ms |
376 KB |
Ok |
5 |
Correct |
2 ms |
376 KB |
Ok |
6 |
Correct |
3 ms |
376 KB |
Ok |
7 |
Correct |
2 ms |
376 KB |
Ok |
8 |
Correct |
2 ms |
504 KB |
Ok |
9 |
Correct |
2 ms |
376 KB |
Ok |
10 |
Correct |
2 ms |
376 KB |
Ok |
11 |
Correct |
2 ms |
376 KB |
Ok |
12 |
Correct |
2 ms |
276 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Ok |
2 |
Correct |
2 ms |
376 KB |
Ok |
3 |
Correct |
2 ms |
420 KB |
Ok |
4 |
Correct |
2 ms |
376 KB |
Ok |
5 |
Correct |
2 ms |
380 KB |
Ok |
6 |
Correct |
5 ms |
584 KB |
Ok |
7 |
Correct |
19 ms |
1272 KB |
Ok |
8 |
Correct |
9 ms |
760 KB |
Ok |
9 |
Correct |
25 ms |
1448 KB |
Ok |
10 |
Correct |
12 ms |
888 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Ok |
2 |
Correct |
2 ms |
416 KB |
Ok |
3 |
Correct |
2 ms |
376 KB |
Ok |
4 |
Correct |
2 ms |
376 KB |
Ok |
5 |
Correct |
2 ms |
376 KB |
Ok |
6 |
Correct |
2 ms |
376 KB |
Ok |
7 |
Correct |
2 ms |
376 KB |
Ok |
8 |
Correct |
2 ms |
376 KB |
Ok |
9 |
Correct |
2 ms |
376 KB |
Ok |
10 |
Correct |
2 ms |
376 KB |
Ok |
11 |
Correct |
2 ms |
376 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Ok |
2 |
Correct |
2 ms |
376 KB |
Ok |
3 |
Correct |
2 ms |
376 KB |
Ok |
4 |
Correct |
2 ms |
376 KB |
Ok |
5 |
Correct |
2 ms |
376 KB |
Ok |
6 |
Correct |
231 ms |
11356 KB |
Ok |
7 |
Correct |
174 ms |
11948 KB |
Ok |
8 |
Correct |
358 ms |
14176 KB |
Ok |
9 |
Correct |
281 ms |
14208 KB |
Ok |
10 |
Correct |
180 ms |
8016 KB |
Ok |
11 |
Correct |
314 ms |
14576 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Ok |
2 |
Correct |
2 ms |
376 KB |
Ok |
3 |
Correct |
2 ms |
376 KB |
Ok |
4 |
Correct |
2 ms |
376 KB |
Ok |
5 |
Correct |
2 ms |
376 KB |
Ok |
6 |
Correct |
3 ms |
376 KB |
Ok |
7 |
Correct |
2 ms |
376 KB |
Ok |
8 |
Correct |
2 ms |
504 KB |
Ok |
9 |
Correct |
2 ms |
376 KB |
Ok |
10 |
Correct |
2 ms |
376 KB |
Ok |
11 |
Correct |
2 ms |
376 KB |
Ok |
12 |
Correct |
2 ms |
276 KB |
Ok |
13 |
Correct |
2 ms |
376 KB |
Ok |
14 |
Correct |
2 ms |
416 KB |
Ok |
15 |
Correct |
2 ms |
376 KB |
Ok |
16 |
Correct |
2 ms |
376 KB |
Ok |
17 |
Correct |
2 ms |
376 KB |
Ok |
18 |
Correct |
2 ms |
376 KB |
Ok |
19 |
Correct |
2 ms |
376 KB |
Ok |
20 |
Correct |
2 ms |
376 KB |
Ok |
21 |
Correct |
2 ms |
376 KB |
Ok |
22 |
Correct |
2 ms |
376 KB |
Ok |
23 |
Correct |
2 ms |
376 KB |
Ok |
24 |
Correct |
5 ms |
504 KB |
Ok |
25 |
Correct |
5 ms |
504 KB |
Ok |
26 |
Correct |
6 ms |
504 KB |
Ok |
27 |
Correct |
5 ms |
504 KB |
Ok |
28 |
Correct |
4 ms |
504 KB |
Ok |
29 |
Correct |
5 ms |
504 KB |
Ok |
30 |
Correct |
4 ms |
504 KB |
Ok |
31 |
Correct |
6 ms |
504 KB |
Ok |
32 |
Correct |
5 ms |
504 KB |
Ok |
33 |
Correct |
5 ms |
504 KB |
Ok |
34 |
Correct |
9 ms |
632 KB |
Ok |
35 |
Correct |
10 ms |
760 KB |
Ok |
36 |
Correct |
9 ms |
760 KB |
Ok |
37 |
Correct |
10 ms |
760 KB |
Ok |
38 |
Correct |
9 ms |
632 KB |
Ok |
39 |
Correct |
9 ms |
760 KB |
Ok |
40 |
Correct |
10 ms |
760 KB |
Ok |
41 |
Correct |
10 ms |
632 KB |
Ok |
42 |
Correct |
10 ms |
760 KB |
Ok |
43 |
Correct |
10 ms |
760 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Ok |
2 |
Correct |
2 ms |
376 KB |
Ok |
3 |
Correct |
2 ms |
376 KB |
Ok |
4 |
Correct |
2 ms |
376 KB |
Ok |
5 |
Correct |
2 ms |
376 KB |
Ok |
6 |
Correct |
3 ms |
376 KB |
Ok |
7 |
Correct |
2 ms |
376 KB |
Ok |
8 |
Correct |
2 ms |
504 KB |
Ok |
9 |
Correct |
2 ms |
376 KB |
Ok |
10 |
Correct |
2 ms |
376 KB |
Ok |
11 |
Correct |
2 ms |
376 KB |
Ok |
12 |
Correct |
2 ms |
276 KB |
Ok |
13 |
Correct |
2 ms |
376 KB |
Ok |
14 |
Correct |
2 ms |
376 KB |
Ok |
15 |
Correct |
2 ms |
420 KB |
Ok |
16 |
Correct |
2 ms |
376 KB |
Ok |
17 |
Correct |
2 ms |
380 KB |
Ok |
18 |
Correct |
5 ms |
584 KB |
Ok |
19 |
Correct |
19 ms |
1272 KB |
Ok |
20 |
Correct |
9 ms |
760 KB |
Ok |
21 |
Correct |
25 ms |
1448 KB |
Ok |
22 |
Correct |
12 ms |
888 KB |
Ok |
23 |
Correct |
2 ms |
376 KB |
Ok |
24 |
Correct |
2 ms |
416 KB |
Ok |
25 |
Correct |
2 ms |
376 KB |
Ok |
26 |
Correct |
2 ms |
376 KB |
Ok |
27 |
Correct |
2 ms |
376 KB |
Ok |
28 |
Correct |
2 ms |
376 KB |
Ok |
29 |
Correct |
2 ms |
376 KB |
Ok |
30 |
Correct |
2 ms |
376 KB |
Ok |
31 |
Correct |
2 ms |
376 KB |
Ok |
32 |
Correct |
2 ms |
376 KB |
Ok |
33 |
Correct |
2 ms |
376 KB |
Ok |
34 |
Correct |
5 ms |
504 KB |
Ok |
35 |
Correct |
5 ms |
504 KB |
Ok |
36 |
Correct |
6 ms |
504 KB |
Ok |
37 |
Correct |
5 ms |
504 KB |
Ok |
38 |
Correct |
4 ms |
504 KB |
Ok |
39 |
Correct |
5 ms |
504 KB |
Ok |
40 |
Correct |
4 ms |
504 KB |
Ok |
41 |
Correct |
6 ms |
504 KB |
Ok |
42 |
Correct |
5 ms |
504 KB |
Ok |
43 |
Correct |
5 ms |
504 KB |
Ok |
44 |
Correct |
9 ms |
632 KB |
Ok |
45 |
Correct |
10 ms |
760 KB |
Ok |
46 |
Correct |
9 ms |
760 KB |
Ok |
47 |
Correct |
10 ms |
760 KB |
Ok |
48 |
Correct |
9 ms |
632 KB |
Ok |
49 |
Correct |
9 ms |
760 KB |
Ok |
50 |
Correct |
10 ms |
760 KB |
Ok |
51 |
Correct |
10 ms |
632 KB |
Ok |
52 |
Correct |
10 ms |
760 KB |
Ok |
53 |
Correct |
10 ms |
760 KB |
Ok |
54 |
Correct |
134 ms |
4136 KB |
Ok |
55 |
Correct |
142 ms |
4596 KB |
Ok |
56 |
Correct |
139 ms |
4468 KB |
Ok |
57 |
Correct |
106 ms |
3628 KB |
Ok |
58 |
Correct |
140 ms |
4480 KB |
Ok |
59 |
Correct |
130 ms |
4212 KB |
Ok |
60 |
Correct |
113 ms |
3828 KB |
Ok |
61 |
Correct |
109 ms |
3952 KB |
Ok |
62 |
Correct |
170 ms |
4852 KB |
Ok |
63 |
Correct |
119 ms |
4084 KB |
Ok |
64 |
Correct |
152 ms |
4588 KB |
Ok |
65 |
Correct |
135 ms |
4340 KB |
Ok |
66 |
Correct |
124 ms |
4084 KB |
Ok |
67 |
Correct |
112 ms |
3828 KB |
Ok |
68 |
Correct |
129 ms |
4312 KB |
Ok |
69 |
Correct |
329 ms |
11508 KB |
Ok |
70 |
Correct |
342 ms |
11716 KB |
Ok |
71 |
Correct |
317 ms |
11508 KB |
Ok |
72 |
Correct |
332 ms |
11252 KB |
Ok |
73 |
Correct |
329 ms |
11636 KB |
Ok |
74 |
Correct |
333 ms |
11252 KB |
Ok |
75 |
Correct |
324 ms |
11276 KB |
Ok |
76 |
Correct |
351 ms |
11516 KB |
Ok |
77 |
Correct |
320 ms |
11252 KB |
Ok |
78 |
Correct |
364 ms |
11384 KB |
Ok |
79 |
Correct |
342 ms |
11760 KB |
Ok |
80 |
Correct |
321 ms |
11404 KB |
Ok |
81 |
Correct |
325 ms |
11636 KB |
Ok |
82 |
Correct |
329 ms |
11380 KB |
Ok |
83 |
Correct |
345 ms |
11588 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Ok |
2 |
Correct |
2 ms |
376 KB |
Ok |
3 |
Correct |
2 ms |
376 KB |
Ok |
4 |
Correct |
2 ms |
376 KB |
Ok |
5 |
Correct |
2 ms |
376 KB |
Ok |
6 |
Correct |
3 ms |
376 KB |
Ok |
7 |
Correct |
2 ms |
376 KB |
Ok |
8 |
Correct |
2 ms |
504 KB |
Ok |
9 |
Correct |
2 ms |
376 KB |
Ok |
10 |
Correct |
2 ms |
376 KB |
Ok |
11 |
Correct |
2 ms |
376 KB |
Ok |
12 |
Correct |
2 ms |
276 KB |
Ok |
13 |
Correct |
2 ms |
376 KB |
Ok |
14 |
Correct |
2 ms |
376 KB |
Ok |
15 |
Correct |
2 ms |
420 KB |
Ok |
16 |
Correct |
2 ms |
376 KB |
Ok |
17 |
Correct |
2 ms |
380 KB |
Ok |
18 |
Correct |
5 ms |
584 KB |
Ok |
19 |
Correct |
19 ms |
1272 KB |
Ok |
20 |
Correct |
9 ms |
760 KB |
Ok |
21 |
Correct |
25 ms |
1448 KB |
Ok |
22 |
Correct |
12 ms |
888 KB |
Ok |
23 |
Correct |
2 ms |
376 KB |
Ok |
24 |
Correct |
2 ms |
416 KB |
Ok |
25 |
Correct |
2 ms |
376 KB |
Ok |
26 |
Correct |
2 ms |
376 KB |
Ok |
27 |
Correct |
2 ms |
376 KB |
Ok |
28 |
Correct |
2 ms |
376 KB |
Ok |
29 |
Correct |
2 ms |
376 KB |
Ok |
30 |
Correct |
2 ms |
376 KB |
Ok |
31 |
Correct |
2 ms |
376 KB |
Ok |
32 |
Correct |
2 ms |
376 KB |
Ok |
33 |
Correct |
2 ms |
376 KB |
Ok |
34 |
Correct |
2 ms |
376 KB |
Ok |
35 |
Correct |
2 ms |
376 KB |
Ok |
36 |
Correct |
2 ms |
376 KB |
Ok |
37 |
Correct |
2 ms |
376 KB |
Ok |
38 |
Correct |
2 ms |
376 KB |
Ok |
39 |
Correct |
231 ms |
11356 KB |
Ok |
40 |
Correct |
174 ms |
11948 KB |
Ok |
41 |
Correct |
358 ms |
14176 KB |
Ok |
42 |
Correct |
281 ms |
14208 KB |
Ok |
43 |
Correct |
180 ms |
8016 KB |
Ok |
44 |
Correct |
314 ms |
14576 KB |
Ok |
45 |
Correct |
5 ms |
504 KB |
Ok |
46 |
Correct |
5 ms |
504 KB |
Ok |
47 |
Correct |
6 ms |
504 KB |
Ok |
48 |
Correct |
5 ms |
504 KB |
Ok |
49 |
Correct |
4 ms |
504 KB |
Ok |
50 |
Correct |
5 ms |
504 KB |
Ok |
51 |
Correct |
4 ms |
504 KB |
Ok |
52 |
Correct |
6 ms |
504 KB |
Ok |
53 |
Correct |
5 ms |
504 KB |
Ok |
54 |
Correct |
5 ms |
504 KB |
Ok |
55 |
Correct |
9 ms |
632 KB |
Ok |
56 |
Correct |
10 ms |
760 KB |
Ok |
57 |
Correct |
9 ms |
760 KB |
Ok |
58 |
Correct |
10 ms |
760 KB |
Ok |
59 |
Correct |
9 ms |
632 KB |
Ok |
60 |
Correct |
9 ms |
760 KB |
Ok |
61 |
Correct |
10 ms |
760 KB |
Ok |
62 |
Correct |
10 ms |
632 KB |
Ok |
63 |
Correct |
10 ms |
760 KB |
Ok |
64 |
Correct |
10 ms |
760 KB |
Ok |
65 |
Correct |
134 ms |
4136 KB |
Ok |
66 |
Correct |
142 ms |
4596 KB |
Ok |
67 |
Correct |
139 ms |
4468 KB |
Ok |
68 |
Correct |
106 ms |
3628 KB |
Ok |
69 |
Correct |
140 ms |
4480 KB |
Ok |
70 |
Correct |
130 ms |
4212 KB |
Ok |
71 |
Correct |
113 ms |
3828 KB |
Ok |
72 |
Correct |
109 ms |
3952 KB |
Ok |
73 |
Correct |
170 ms |
4852 KB |
Ok |
74 |
Correct |
119 ms |
4084 KB |
Ok |
75 |
Correct |
152 ms |
4588 KB |
Ok |
76 |
Correct |
135 ms |
4340 KB |
Ok |
77 |
Correct |
124 ms |
4084 KB |
Ok |
78 |
Correct |
112 ms |
3828 KB |
Ok |
79 |
Correct |
129 ms |
4312 KB |
Ok |
80 |
Correct |
329 ms |
11508 KB |
Ok |
81 |
Correct |
342 ms |
11716 KB |
Ok |
82 |
Correct |
317 ms |
11508 KB |
Ok |
83 |
Correct |
332 ms |
11252 KB |
Ok |
84 |
Correct |
329 ms |
11636 KB |
Ok |
85 |
Correct |
333 ms |
11252 KB |
Ok |
86 |
Correct |
324 ms |
11276 KB |
Ok |
87 |
Correct |
351 ms |
11516 KB |
Ok |
88 |
Correct |
320 ms |
11252 KB |
Ok |
89 |
Correct |
364 ms |
11384 KB |
Ok |
90 |
Correct |
342 ms |
11760 KB |
Ok |
91 |
Correct |
321 ms |
11404 KB |
Ok |
92 |
Correct |
325 ms |
11636 KB |
Ok |
93 |
Correct |
329 ms |
11380 KB |
Ok |
94 |
Correct |
345 ms |
11588 KB |
Ok |
95 |
Correct |
353 ms |
10108 KB |
Ok |
96 |
Correct |
510 ms |
14736 KB |
Ok |
97 |
Correct |
485 ms |
12844 KB |
Ok |
98 |
Correct |
353 ms |
11544 KB |
Ok |
99 |
Correct |
461 ms |
11964 KB |
Ok |
100 |
Correct |
463 ms |
12620 KB |
Ok |
101 |
Correct |
435 ms |
12708 KB |
Ok |
102 |
Correct |
454 ms |
12552 KB |
Ok |
103 |
Correct |
700 ms |
13160 KB |
Ok |
104 |
Correct |
508 ms |
14088 KB |
Ok |
105 |
Correct |
493 ms |
14400 KB |
Ok |
106 |
Correct |
424 ms |
12968 KB |
Ok |
107 |
Correct |
485 ms |
13636 KB |
Ok |
108 |
Correct |
529 ms |
14680 KB |
Ok |
109 |
Correct |
493 ms |
14056 KB |
Ok |
110 |
Correct |
1903 ms |
45300 KB |
Ok |
111 |
Execution timed out |
2039 ms |
40000 KB |
Time limit exceeded |
112 |
Halted |
0 ms |
0 KB |
- |