oj.uz

Submission #379200

# Submission time Handle Problem Language Result Execution time Memory
379200 2021-03-17T13:47:38 Z cheissmart Nice sequence (IZhO18_sequence) C++14
100 / 100
 513 ms 35024 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

void solve() {
	int n, m;
	cin >> n >> m;
	int l = n + m - __gcd(n, m) - 1;
	vi in(l + 1), p(l + 1);
	for(int i = 0; i <= l; i++) {
		// i ---> i + m
		// i - n <--- i
		if(i + m <= l) in[i + m]++;
		if(i - n >= 0) in[i - n]++;
	}
	vi q;
	for(int i = 0; i <= l; i++) if(in[i] == 0) q.PB(i);
	for(int i = 0; i < int(q.size()); i++) {
		p[q[i]] = i;
		if(q[i] + m <= l) {
		in[q[i] + m]--;
			if(in[q[i] + m] == 0) q.PB(q[i] + m);
		}
		if(q[i] - n >= 0) {
			in[q[i] - n]--;
			if(in[q[i] - n] == 0) q.PB(q[i] - n);
		}
	}
	cout << l << '\n';
	for(int i = 1; i <= l; i++) {
		cout << p[i] - p[i - 1] << ' ';
	}
	cout << '\n';
}

signed main()
{
	IO_OP;

	int t;
	cin >> t;
	while(t--)
		solve();		
		
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 384 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 3 ms 492 KB Ok
7 Correct 11 ms 1004 KB Ok
8 Correct 5 ms 620 KB Ok
9 Correct 12 ms 984 KB Ok
10 Correct 7 ms 620 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 91 ms 5012 KB Ok
7 Correct 78 ms 4432 KB Ok
8 Correct 150 ms 7536 KB Ok
9 Correct 115 ms 8132 KB Ok
10 Correct 79 ms 3432 KB Ok
11 Correct 109 ms 7300 KB Ok

Subtask #5
14.0 / 14.0

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

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 384 KB Ok
15 Correct 1 ms 384 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 3 ms 492 KB Ok
19 Correct 11 ms 1004 KB Ok
20 Correct 5 ms 620 KB Ok
21 Correct 12 ms 984 KB Ok
22 Correct 7 ms 620 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 3 ms 364 KB Ok
35 Correct 2 ms 492 KB Ok
36 Correct 3 ms 492 KB Ok
37 Correct 2 ms 492 KB Ok
38 Correct 2 ms 364 KB Ok
39 Correct 2 ms 364 KB Ok
40 Correct 2 ms 364 KB Ok
41 Correct 2 ms 492 KB Ok
42 Correct 2 ms 492 KB Ok
43 Correct 2 ms 492 KB Ok
44 Correct 4 ms 492 KB Ok
45 Correct 5 ms 620 KB Ok
46 Correct 4 ms 492 KB Ok
47 Correct 4 ms 620 KB Ok
48 Correct 5 ms 492 KB Ok
49 Correct 4 ms 492 KB Ok
50 Correct 5 ms 492 KB Ok
51 Correct 4 ms 492 KB Ok
52 Correct 4 ms 492 KB Ok
53 Correct 5 ms 620 KB Ok
54 Correct 72 ms 3304 KB Ok
55 Correct 80 ms 3368 KB Ok
56 Correct 80 ms 3240 KB Ok
57 Correct 72 ms 2760 KB Ok
58 Correct 72 ms 3096 KB Ok
59 Correct 72 ms 3208 KB Ok
60 Correct 63 ms 2928 KB Ok
61 Correct 62 ms 2920 KB Ok
62 Correct 86 ms 3484 KB Ok
63 Correct 67 ms 2908 KB Ok
64 Correct 83 ms 3264 KB Ok
65 Correct 75 ms 3412 KB Ok
66 Correct 70 ms 3124 KB Ok
67 Correct 60 ms 3012 KB Ok
68 Correct 72 ms 3016 KB Ok
69 Correct 116 ms 7320 KB Ok
70 Correct 134 ms 8732 KB Ok
71 Correct 114 ms 6552 KB Ok
72 Correct 116 ms 7700 KB Ok
73 Correct 115 ms 7060 KB Ok
74 Correct 116 ms 6048 KB Ok
75 Correct 117 ms 6292 KB Ok
76 Correct 130 ms 8224 KB Ok
77 Correct 111 ms 5668 KB Ok
78 Correct 119 ms 8060 KB Ok
79 Correct 118 ms 7448 KB Ok
80 Correct 119 ms 7060 KB Ok
81 Correct 118 ms 7712 KB Ok
82 Correct 117 ms 7324 KB Ok
83 Correct 120 ms 6192 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 384 KB Ok
15 Correct 1 ms 384 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 3 ms 492 KB Ok
19 Correct 11 ms 1004 KB Ok
20 Correct 5 ms 620 KB Ok
21 Correct 12 ms 984 KB Ok
22 Correct 7 ms 620 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 384 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 1 ms 364 KB Ok
39 Correct 91 ms 5012 KB Ok
40 Correct 78 ms 4432 KB Ok
41 Correct 150 ms 7536 KB Ok
42 Correct 115 ms 8132 KB Ok
43 Correct 79 ms 3432 KB Ok
44 Correct 109 ms 7300 KB Ok
45 Correct 3 ms 364 KB Ok
46 Correct 2 ms 492 KB Ok
47 Correct 3 ms 492 KB Ok
48 Correct 2 ms 492 KB Ok
49 Correct 2 ms 364 KB Ok
50 Correct 2 ms 364 KB Ok
51 Correct 2 ms 364 KB Ok
52 Correct 2 ms 492 KB Ok
53 Correct 2 ms 492 KB Ok
54 Correct 2 ms 492 KB Ok
55 Correct 4 ms 492 KB Ok
56 Correct 5 ms 620 KB Ok
57 Correct 4 ms 492 KB Ok
58 Correct 4 ms 620 KB Ok
59 Correct 5 ms 492 KB Ok
60 Correct 4 ms 492 KB Ok
61 Correct 5 ms 492 KB Ok
62 Correct 4 ms 492 KB Ok
63 Correct 4 ms 492 KB Ok
64 Correct 5 ms 620 KB Ok
65 Correct 72 ms 3304 KB Ok
66 Correct 80 ms 3368 KB Ok
67 Correct 80 ms 3240 KB Ok
68 Correct 72 ms 2760 KB Ok
69 Correct 72 ms 3096 KB Ok
70 Correct 72 ms 3208 KB Ok
71 Correct 63 ms 2928 KB Ok
72 Correct 62 ms 2920 KB Ok
73 Correct 86 ms 3484 KB Ok
74 Correct 67 ms 2908 KB Ok
75 Correct 83 ms 3264 KB Ok
76 Correct 75 ms 3412 KB Ok
77 Correct 70 ms 3124 KB Ok
78 Correct 60 ms 3012 KB Ok
79 Correct 72 ms 3016 KB Ok
80 Correct 116 ms 7320 KB Ok
81 Correct 134 ms 8732 KB Ok
82 Correct 114 ms 6552 KB Ok
83 Correct 116 ms 7700 KB Ok
84 Correct 115 ms 7060 KB Ok
85 Correct 116 ms 6048 KB Ok
86 Correct 117 ms 6292 KB Ok
87 Correct 130 ms 8224 KB Ok
88 Correct 111 ms 5668 KB Ok
89 Correct 119 ms 8060 KB Ok
90 Correct 118 ms 7448 KB Ok
91 Correct 119 ms 7060 KB Ok
92 Correct 118 ms 7712 KB Ok
93 Correct 117 ms 7324 KB Ok
94 Correct 120 ms 6192 KB Ok
95 Correct 173 ms 7236 KB Ok
96 Correct 281 ms 11100 KB Ok
97 Correct 251 ms 9552 KB Ok
98 Correct 190 ms 7608 KB Ok
99 Correct 230 ms 8652 KB Ok
100 Correct 230 ms 8432 KB Ok
101 Correct 231 ms 10036 KB Ok
102 Correct 237 ms 9988 KB Ok
103 Correct 216 ms 8784 KB Ok
104 Correct 260 ms 10056 KB Ok
105 Correct 259 ms 11396 KB Ok
106 Correct 209 ms 9168 KB Ok
107 Correct 243 ms 10688 KB Ok
108 Correct 258 ms 10908 KB Ok
109 Correct 233 ms 8812 KB Ok
110 Correct 481 ms 25228 KB Ok
111 Correct 496 ms 34780 KB Ok
112 Correct 503 ms 27080 KB Ok
113 Correct 513 ms 31440 KB Ok
114 Correct 484 ms 32488 KB Ok
115 Correct 508 ms 31824 KB Ok
116 Correct 488 ms 31668 KB Ok
117 Correct 471 ms 32664 KB Ok
118 Correct 484 ms 27960 KB Ok
119 Correct 481 ms 33568 KB Ok
120 Correct 473 ms 28316 KB Ok
121 Correct 475 ms 27328 KB Ok
122 Correct 475 ms 30132 KB Ok
123 Correct 489 ms 35024 KB Ok
124 Correct 473 ms 23968 KB Ok
125 Correct 424 ms 17124 KB Ok