#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 = 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:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("Ofast")
sequence.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
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 |
504 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 |
380 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 |
12 |
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 |
380 KB |
Ok |
6 |
Correct |
5 ms |
504 KB |
Ok |
7 |
Correct |
19 ms |
1272 KB |
Ok |
8 |
Correct |
9 ms |
760 KB |
Ok |
9 |
Correct |
22 ms |
1400 KB |
Ok |
10 |
Correct |
12 ms |
932 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 |
292 KB |
Ok |
5 |
Correct |
2 ms |
376 KB |
Ok |
6 |
Correct |
2 ms |
376 KB |
Ok |
7 |
Correct |
2 ms |
380 KB |
Ok |
8 |
Correct |
2 ms |
424 KB |
Ok |
9 |
Correct |
2 ms |
376 KB |
Ok |
10 |
Correct |
2 ms |
376 KB |
Ok |
11 |
Correct |
2 ms |
380 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 |
219 ms |
11408 KB |
Ok |
7 |
Correct |
166 ms |
11884 KB |
Ok |
8 |
Correct |
351 ms |
14184 KB |
Ok |
9 |
Correct |
289 ms |
14168 KB |
Ok |
10 |
Correct |
169 ms |
7920 KB |
Ok |
11 |
Correct |
285 ms |
14824 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 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 |
380 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 |
12 |
Correct |
2 ms |
376 KB |
Ok |
13 |
Correct |
2 ms |
376 KB |
Ok |
14 |
Correct |
2 ms |
376 KB |
Ok |
15 |
Correct |
2 ms |
376 KB |
Ok |
16 |
Correct |
2 ms |
292 KB |
Ok |
17 |
Correct |
2 ms |
376 KB |
Ok |
18 |
Correct |
2 ms |
376 KB |
Ok |
19 |
Correct |
2 ms |
380 KB |
Ok |
20 |
Correct |
2 ms |
424 KB |
Ok |
21 |
Correct |
2 ms |
376 KB |
Ok |
22 |
Correct |
2 ms |
376 KB |
Ok |
23 |
Correct |
2 ms |
380 KB |
Ok |
24 |
Correct |
5 ms |
504 KB |
Ok |
25 |
Correct |
5 ms |
504 KB |
Ok |
26 |
Correct |
5 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 |
376 KB |
Ok |
31 |
Correct |
5 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 |
9 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 |
732 KB |
Ok |
40 |
Correct |
10 ms |
548 KB |
Ok |
41 |
Correct |
9 ms |
632 KB |
Ok |
42 |
Correct |
10 ms |
760 KB |
Ok |
43 |
Correct |
9 ms |
760 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 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 |
380 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 |
12 |
Correct |
2 ms |
376 KB |
Ok |
13 |
Correct |
2 ms |
376 KB |
Ok |
14 |
Correct |
2 ms |
376 KB |
Ok |
15 |
Correct |
2 ms |
376 KB |
Ok |
16 |
Correct |
2 ms |
376 KB |
Ok |
17 |
Correct |
2 ms |
380 KB |
Ok |
18 |
Correct |
5 ms |
504 KB |
Ok |
19 |
Correct |
19 ms |
1272 KB |
Ok |
20 |
Correct |
9 ms |
760 KB |
Ok |
21 |
Correct |
22 ms |
1400 KB |
Ok |
22 |
Correct |
12 ms |
932 KB |
Ok |
23 |
Correct |
2 ms |
376 KB |
Ok |
24 |
Correct |
2 ms |
376 KB |
Ok |
25 |
Correct |
2 ms |
376 KB |
Ok |
26 |
Correct |
2 ms |
292 KB |
Ok |
27 |
Correct |
2 ms |
376 KB |
Ok |
28 |
Correct |
2 ms |
376 KB |
Ok |
29 |
Correct |
2 ms |
380 KB |
Ok |
30 |
Correct |
2 ms |
424 KB |
Ok |
31 |
Correct |
2 ms |
376 KB |
Ok |
32 |
Correct |
2 ms |
376 KB |
Ok |
33 |
Correct |
2 ms |
380 KB |
Ok |
34 |
Correct |
5 ms |
504 KB |
Ok |
35 |
Correct |
5 ms |
504 KB |
Ok |
36 |
Correct |
5 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 |
376 KB |
Ok |
41 |
Correct |
5 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 |
9 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 |
732 KB |
Ok |
50 |
Correct |
10 ms |
548 KB |
Ok |
51 |
Correct |
9 ms |
632 KB |
Ok |
52 |
Correct |
10 ms |
760 KB |
Ok |
53 |
Correct |
9 ms |
760 KB |
Ok |
54 |
Correct |
132 ms |
4116 KB |
Ok |
55 |
Correct |
145 ms |
4596 KB |
Ok |
56 |
Correct |
154 ms |
4492 KB |
Ok |
57 |
Correct |
108 ms |
3572 KB |
Ok |
58 |
Correct |
142 ms |
4420 KB |
Ok |
59 |
Correct |
134 ms |
4212 KB |
Ok |
60 |
Correct |
114 ms |
3884 KB |
Ok |
61 |
Correct |
111 ms |
3828 KB |
Ok |
62 |
Correct |
159 ms |
4724 KB |
Ok |
63 |
Correct |
122 ms |
4056 KB |
Ok |
64 |
Correct |
152 ms |
4472 KB |
Ok |
65 |
Correct |
138 ms |
4336 KB |
Ok |
66 |
Correct |
122 ms |
4080 KB |
Ok |
67 |
Correct |
109 ms |
3700 KB |
Ok |
68 |
Correct |
132 ms |
4208 KB |
Ok |
69 |
Correct |
311 ms |
11332 KB |
Ok |
70 |
Correct |
324 ms |
11848 KB |
Ok |
71 |
Correct |
298 ms |
11348 KB |
Ok |
72 |
Correct |
304 ms |
11252 KB |
Ok |
73 |
Correct |
302 ms |
11504 KB |
Ok |
74 |
Correct |
296 ms |
11252 KB |
Ok |
75 |
Correct |
297 ms |
11272 KB |
Ok |
76 |
Correct |
329 ms |
11376 KB |
Ok |
77 |
Correct |
292 ms |
11268 KB |
Ok |
78 |
Correct |
326 ms |
11144 KB |
Ok |
79 |
Correct |
304 ms |
11632 KB |
Ok |
80 |
Correct |
303 ms |
11376 KB |
Ok |
81 |
Correct |
297 ms |
11756 KB |
Ok |
82 |
Correct |
310 ms |
11324 KB |
Ok |
83 |
Correct |
300 ms |
11484 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 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 |
380 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 |
12 |
Correct |
2 ms |
376 KB |
Ok |
13 |
Correct |
2 ms |
376 KB |
Ok |
14 |
Correct |
2 ms |
376 KB |
Ok |
15 |
Correct |
2 ms |
376 KB |
Ok |
16 |
Correct |
2 ms |
376 KB |
Ok |
17 |
Correct |
2 ms |
380 KB |
Ok |
18 |
Correct |
5 ms |
504 KB |
Ok |
19 |
Correct |
19 ms |
1272 KB |
Ok |
20 |
Correct |
9 ms |
760 KB |
Ok |
21 |
Correct |
22 ms |
1400 KB |
Ok |
22 |
Correct |
12 ms |
932 KB |
Ok |
23 |
Correct |
2 ms |
376 KB |
Ok |
24 |
Correct |
2 ms |
376 KB |
Ok |
25 |
Correct |
2 ms |
376 KB |
Ok |
26 |
Correct |
2 ms |
292 KB |
Ok |
27 |
Correct |
2 ms |
376 KB |
Ok |
28 |
Correct |
2 ms |
376 KB |
Ok |
29 |
Correct |
2 ms |
380 KB |
Ok |
30 |
Correct |
2 ms |
424 KB |
Ok |
31 |
Correct |
2 ms |
376 KB |
Ok |
32 |
Correct |
2 ms |
376 KB |
Ok |
33 |
Correct |
2 ms |
380 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 |
219 ms |
11408 KB |
Ok |
40 |
Correct |
166 ms |
11884 KB |
Ok |
41 |
Correct |
351 ms |
14184 KB |
Ok |
42 |
Correct |
289 ms |
14168 KB |
Ok |
43 |
Correct |
169 ms |
7920 KB |
Ok |
44 |
Correct |
285 ms |
14824 KB |
Ok |
45 |
Correct |
5 ms |
504 KB |
Ok |
46 |
Correct |
5 ms |
504 KB |
Ok |
47 |
Correct |
5 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 |
376 KB |
Ok |
52 |
Correct |
5 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 |
9 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 |
732 KB |
Ok |
61 |
Correct |
10 ms |
548 KB |
Ok |
62 |
Correct |
9 ms |
632 KB |
Ok |
63 |
Correct |
10 ms |
760 KB |
Ok |
64 |
Correct |
9 ms |
760 KB |
Ok |
65 |
Correct |
132 ms |
4116 KB |
Ok |
66 |
Correct |
145 ms |
4596 KB |
Ok |
67 |
Correct |
154 ms |
4492 KB |
Ok |
68 |
Correct |
108 ms |
3572 KB |
Ok |
69 |
Correct |
142 ms |
4420 KB |
Ok |
70 |
Correct |
134 ms |
4212 KB |
Ok |
71 |
Correct |
114 ms |
3884 KB |
Ok |
72 |
Correct |
111 ms |
3828 KB |
Ok |
73 |
Correct |
159 ms |
4724 KB |
Ok |
74 |
Correct |
122 ms |
4056 KB |
Ok |
75 |
Correct |
152 ms |
4472 KB |
Ok |
76 |
Correct |
138 ms |
4336 KB |
Ok |
77 |
Correct |
122 ms |
4080 KB |
Ok |
78 |
Correct |
109 ms |
3700 KB |
Ok |
79 |
Correct |
132 ms |
4208 KB |
Ok |
80 |
Correct |
311 ms |
11332 KB |
Ok |
81 |
Correct |
324 ms |
11848 KB |
Ok |
82 |
Correct |
298 ms |
11348 KB |
Ok |
83 |
Correct |
304 ms |
11252 KB |
Ok |
84 |
Correct |
302 ms |
11504 KB |
Ok |
85 |
Correct |
296 ms |
11252 KB |
Ok |
86 |
Correct |
297 ms |
11272 KB |
Ok |
87 |
Correct |
329 ms |
11376 KB |
Ok |
88 |
Correct |
292 ms |
11268 KB |
Ok |
89 |
Correct |
326 ms |
11144 KB |
Ok |
90 |
Correct |
304 ms |
11632 KB |
Ok |
91 |
Correct |
303 ms |
11376 KB |
Ok |
92 |
Correct |
297 ms |
11756 KB |
Ok |
93 |
Correct |
310 ms |
11324 KB |
Ok |
94 |
Correct |
300 ms |
11484 KB |
Ok |
95 |
Correct |
344 ms |
10004 KB |
Ok |
96 |
Correct |
510 ms |
14548 KB |
Ok |
97 |
Correct |
597 ms |
12824 KB |
Ok |
98 |
Correct |
367 ms |
11388 KB |
Ok |
99 |
Correct |
418 ms |
11592 KB |
Ok |
100 |
Correct |
460 ms |
12444 KB |
Ok |
101 |
Correct |
439 ms |
12712 KB |
Ok |
102 |
Correct |
436 ms |
12340 KB |
Ok |
103 |
Correct |
448 ms |
13024 KB |
Ok |
104 |
Correct |
504 ms |
14160 KB |
Ok |
105 |
Correct |
505 ms |
14268 KB |
Ok |
106 |
Correct |
468 ms |
12860 KB |
Ok |
107 |
Correct |
481 ms |
13368 KB |
Ok |
108 |
Correct |
524 ms |
14792 KB |
Ok |
109 |
Correct |
511 ms |
14032 KB |
Ok |
110 |
Correct |
1498 ms |
44668 KB |
Ok |
111 |
Correct |
1902 ms |
46712 KB |
Ok |
112 |
Correct |
1518 ms |
47332 KB |
Ok |
113 |
Correct |
1704 ms |
45916 KB |
Ok |
114 |
Correct |
1557 ms |
47460 KB |
Ok |
115 |
Correct |
1665 ms |
46568 KB |
Ok |
116 |
Correct |
1686 ms |
47732 KB |
Ok |
117 |
Correct |
1740 ms |
45928 KB |
Ok |
118 |
Correct |
1518 ms |
47156 KB |
Ok |
119 |
Correct |
1821 ms |
45832 KB |
Ok |
120 |
Correct |
1658 ms |
46604 KB |
Ok |
121 |
Correct |
1556 ms |
46104 KB |
Ok |
122 |
Correct |
1661 ms |
46860 KB |
Ok |
123 |
Correct |
1801 ms |
46704 KB |
Ok |
124 |
Correct |
1485 ms |
47796 KB |
Ok |
125 |
Correct |
1313 ms |
29424 KB |
Ok |