oj.uz

Submission #797341

# Submission time Handle Problem Language Result Execution time Memory
797341 2023-07-29T09:35:58 Z kingfran1907 Nice sequence (IZhO18_sequence) C++14
100 / 100
 361 ms 42788 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long llint;
const int maxn = 1e6+10;

int t;
int n, m;
int dis[maxn];
int out[maxn];
int sol;

int cnt;
void dfs(int x) {
	if (x < 0 || x > sol) return;
	if (dis[x] != -1) return;
	dis[x] = maxn;
	dfs(x + n); dfs(x - m);
	dis[x] = cnt++;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		sol = n + m - 1 - __gcd(n, m);
		printf("%d\n", sol);
		if (n == m) {
			for (int i = 0; i < sol; i++) printf("1 ");
			printf("\n");
			continue;
		}
		
		for (int i = 0; i <= sol; i++) dis[i] = -1;
		cnt = 0;
		for (int i = 0; i <= sol; i++) {
			if (dis[i] == -1) dfs(i);
		}
		//for (int i = 0; i <= sol; i++) printf("%d ", dis[i]); printf("\n");
		
		for (int i = 0; i < sol; i++) out[i] = dis[i + 1] - dis[i];
		for (int i = n; i <= sol; i++) assert(dis[i] - dis[i - n] <= -1);
		for (int i = m; i <= sol; i++) assert(dis[i] - dis[i - m] >= 1);
		for (int i = 0; i < sol; i++) 
			printf("%d ", out[i]);
		printf("\n");
	}
	return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~
sequence.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 2 ms 340 KB Ok
7 Correct 6 ms 852 KB Ok
8 Correct 4 ms 596 KB Ok
9 Correct 7 ms 940 KB Ok
10 Correct 4 ms 724 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 1 ms 216 KB Ok
6 Correct 69 ms 6940 KB Ok
7 Correct 51 ms 10060 KB Ok
8 Correct 103 ms 13036 KB Ok
9 Correct 75 ms 11472 KB Ok
10 Correct 43 ms 5176 KB Ok
11 Correct 71 ms 8352 KB Ok

Subtask #5
14.0 / 14.0

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

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 0 ms 212 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 212 KB Ok
12 Correct 0 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 0 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 2 ms 340 KB Ok
19 Correct 6 ms 852 KB Ok
20 Correct 4 ms 596 KB Ok
21 Correct 7 ms 940 KB Ok
22 Correct 4 ms 724 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 0 ms 212 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 1 ms 212 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 0 ms 216 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 2 ms 340 KB Ok
35 Correct 2 ms 340 KB Ok
36 Correct 2 ms 340 KB Ok
37 Correct 1 ms 340 KB Ok
38 Correct 2 ms 340 KB Ok
39 Correct 1 ms 340 KB Ok
40 Correct 1 ms 340 KB Ok
41 Correct 2 ms 340 KB Ok
42 Correct 2 ms 340 KB Ok
43 Correct 2 ms 340 KB Ok
44 Correct 3 ms 468 KB Ok
45 Correct 3 ms 468 KB Ok
46 Correct 3 ms 468 KB Ok
47 Correct 3 ms 468 KB Ok
48 Correct 4 ms 640 KB Ok
49 Correct 3 ms 468 KB Ok
50 Correct 3 ms 596 KB Ok
51 Correct 3 ms 468 KB Ok
52 Correct 3 ms 468 KB Ok
53 Correct 5 ms 600 KB Ok
54 Correct 46 ms 2616 KB Ok
55 Correct 51 ms 2984 KB Ok
56 Correct 74 ms 3008 KB Ok
57 Correct 34 ms 2272 KB Ok
58 Correct 67 ms 2412 KB Ok
59 Correct 41 ms 2300 KB Ok
60 Correct 36 ms 2128 KB Ok
61 Correct 35 ms 2224 KB Ok
62 Correct 53 ms 2672 KB Ok
63 Correct 36 ms 2424 KB Ok
64 Correct 50 ms 3032 KB Ok
65 Correct 47 ms 2636 KB Ok
66 Correct 40 ms 2384 KB Ok
67 Correct 31 ms 2364 KB Ok
68 Correct 43 ms 2528 KB Ok
69 Correct 83 ms 9948 KB Ok
70 Correct 81 ms 10684 KB Ok
71 Correct 80 ms 10036 KB Ok
72 Correct 80 ms 9980 KB Ok
73 Correct 80 ms 9608 KB Ok
74 Correct 80 ms 9320 KB Ok
75 Correct 80 ms 9392 KB Ok
76 Correct 82 ms 10260 KB Ok
77 Correct 80 ms 8912 KB Ok
78 Correct 81 ms 9420 KB Ok
79 Correct 80 ms 9884 KB Ok
80 Correct 81 ms 10124 KB Ok
81 Correct 83 ms 9516 KB Ok
82 Correct 91 ms 9884 KB Ok
83 Correct 80 ms 9528 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 0 ms 212 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 212 KB Ok
12 Correct 0 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 0 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 2 ms 340 KB Ok
19 Correct 6 ms 852 KB Ok
20 Correct 4 ms 596 KB Ok
21 Correct 7 ms 940 KB Ok
22 Correct 4 ms 724 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 0 ms 212 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 1 ms 212 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 0 ms 216 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 1 ms 216 KB Ok
35 Correct 0 ms 212 KB Ok
36 Correct 0 ms 212 KB Ok
37 Correct 0 ms 212 KB Ok
38 Correct 1 ms 216 KB Ok
39 Correct 69 ms 6940 KB Ok
40 Correct 51 ms 10060 KB Ok
41 Correct 103 ms 13036 KB Ok
42 Correct 75 ms 11472 KB Ok
43 Correct 43 ms 5176 KB Ok
44 Correct 71 ms 8352 KB Ok
45 Correct 2 ms 340 KB Ok
46 Correct 2 ms 340 KB Ok
47 Correct 2 ms 340 KB Ok
48 Correct 1 ms 340 KB Ok
49 Correct 2 ms 340 KB Ok
50 Correct 1 ms 340 KB Ok
51 Correct 1 ms 340 KB Ok
52 Correct 2 ms 340 KB Ok
53 Correct 2 ms 340 KB Ok
54 Correct 2 ms 340 KB Ok
55 Correct 3 ms 468 KB Ok
56 Correct 3 ms 468 KB Ok
57 Correct 3 ms 468 KB Ok
58 Correct 3 ms 468 KB Ok
59 Correct 4 ms 640 KB Ok
60 Correct 3 ms 468 KB Ok
61 Correct 3 ms 596 KB Ok
62 Correct 3 ms 468 KB Ok
63 Correct 3 ms 468 KB Ok
64 Correct 5 ms 600 KB Ok
65 Correct 46 ms 2616 KB Ok
66 Correct 51 ms 2984 KB Ok
67 Correct 74 ms 3008 KB Ok
68 Correct 34 ms 2272 KB Ok
69 Correct 67 ms 2412 KB Ok
70 Correct 41 ms 2300 KB Ok
71 Correct 36 ms 2128 KB Ok
72 Correct 35 ms 2224 KB Ok
73 Correct 53 ms 2672 KB Ok
74 Correct 36 ms 2424 KB Ok
75 Correct 50 ms 3032 KB Ok
76 Correct 47 ms 2636 KB Ok
77 Correct 40 ms 2384 KB Ok
78 Correct 31 ms 2364 KB Ok
79 Correct 43 ms 2528 KB Ok
80 Correct 83 ms 9948 KB Ok
81 Correct 81 ms 10684 KB Ok
82 Correct 80 ms 10036 KB Ok
83 Correct 80 ms 9980 KB Ok
84 Correct 80 ms 9608 KB Ok
85 Correct 80 ms 9320 KB Ok
86 Correct 80 ms 9392 KB Ok
87 Correct 82 ms 10260 KB Ok
88 Correct 80 ms 8912 KB Ok
89 Correct 81 ms 9420 KB Ok
90 Correct 80 ms 9884 KB Ok
91 Correct 81 ms 10124 KB Ok
92 Correct 83 ms 9516 KB Ok
93 Correct 91 ms 9884 KB Ok
94 Correct 80 ms 9528 KB Ok
95 Correct 104 ms 6412 KB Ok
96 Correct 156 ms 8660 KB Ok
97 Correct 158 ms 7664 KB Ok
98 Correct 102 ms 6732 KB Ok
99 Correct 145 ms 7048 KB Ok
100 Correct 141 ms 7200 KB Ok
101 Correct 140 ms 7736 KB Ok
102 Correct 121 ms 7540 KB Ok
103 Correct 122 ms 7532 KB Ok
104 Correct 152 ms 8820 KB Ok
105 Correct 151 ms 8524 KB Ok
106 Correct 108 ms 8344 KB Ok
107 Correct 134 ms 8056 KB Ok
108 Correct 162 ms 8780 KB Ok
109 Correct 135 ms 8740 KB Ok
110 Correct 321 ms 40036 KB Ok
111 Correct 328 ms 42304 KB Ok
112 Correct 325 ms 39736 KB Ok
113 Correct 338 ms 42476 KB Ok
114 Correct 354 ms 42788 KB Ok
115 Correct 326 ms 40236 KB Ok
116 Correct 333 ms 42472 KB Ok
117 Correct 327 ms 41808 KB Ok
118 Correct 361 ms 42024 KB Ok
119 Correct 323 ms 41120 KB Ok
120 Correct 327 ms 41152 KB Ok
121 Correct 330 ms 40648 KB Ok
122 Correct 325 ms 41096 KB Ok
123 Correct 337 ms 42688 KB Ok
124 Correct 323 ms 37636 KB Ok
125 Correct 288 ms 25928 KB Ok