oj.uz

Submission #797332

# Submission time Handle Problem Language Result Execution time Memory
797332 2023-07-29T09:25:42 Z kingfran1907 Nice sequence (IZhO18_sequence) C++14
61 / 100
 2000 ms 11628 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;
	dis[x] = cnt++;
	dfs(x + n); dfs(x - m);
}

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;
		}
		
		memset(dis, -1, sizeof dis);
		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++) dis[i] *= -1;
		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:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~
sequence.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Ok
2 Correct 2 ms 4180 KB Ok
3 Correct 3 ms 4152 KB Ok
4 Correct 2 ms 4180 KB Ok
5 Correct 2 ms 4180 KB Ok
6 Correct 16 ms 4280 KB Ok
7 Correct 256 ms 4880 KB Ok
8 Correct 44 ms 4400 KB Ok
9 Correct 522 ms 4864 KB Ok
10 Correct 92 ms 4560 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Ok
2 Correct 2 ms 4124 KB Ok
3 Correct 3 ms 4152 KB Ok
4 Correct 2 ms 4180 KB Ok
5 Correct 3 ms 4180 KB Ok
6 Execution timed out 2077 ms 4376 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Ok
2 Correct 2 ms 4180 KB Ok
3 Correct 2 ms 4180 KB Ok
4 Correct 2 ms 4180 KB Ok
5 Correct 2 ms 4180 KB Ok
6 Correct 2 ms 4180 KB Ok
7 Correct 2 ms 4148 KB Ok
8 Correct 2 ms 4180 KB Ok
9 Correct 2 ms 4180 KB Ok
10 Correct 2 ms 4180 KB Ok
11 Correct 2 ms 4180 KB Ok
12 Correct 0 ms 212 KB Ok
13 Correct 2 ms 4180 KB Ok
14 Correct 2 ms 4180 KB Ok
15 Correct 2 ms 4180 KB Ok
16 Correct 2 ms 4156 KB Ok
17 Correct 2 ms 4180 KB Ok
18 Correct 2 ms 4148 KB Ok
19 Correct 2 ms 4180 KB Ok
20 Correct 2 ms 4180 KB Ok
21 Correct 3 ms 4180 KB Ok
22 Correct 3 ms 4180 KB Ok
23 Correct 2 ms 4180 KB Ok
24 Correct 4 ms 4180 KB Ok
25 Correct 4 ms 4268 KB Ok
26 Correct 3 ms 4280 KB Ok
27 Correct 3 ms 4180 KB Ok
28 Correct 4 ms 4180 KB Ok
29 Correct 3 ms 4264 KB Ok
30 Correct 3 ms 4180 KB Ok
31 Correct 4 ms 4180 KB Ok
32 Correct 4 ms 4180 KB Ok
33 Correct 3 ms 4180 KB Ok
34 Correct 6 ms 4308 KB Ok
35 Correct 7 ms 4308 KB Ok
36 Correct 8 ms 4308 KB Ok
37 Correct 6 ms 4308 KB Ok
38 Correct 6 ms 4308 KB Ok
39 Correct 6 ms 4308 KB Ok
40 Correct 7 ms 4376 KB Ok
41 Correct 6 ms 4308 KB Ok
42 Correct 6 ms 4308 KB Ok
43 Correct 6 ms 4404 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Ok
2 Correct 2 ms 4180 KB Ok
3 Correct 2 ms 4180 KB Ok
4 Correct 2 ms 4180 KB Ok
5 Correct 2 ms 4180 KB Ok
6 Correct 2 ms 4180 KB Ok
7 Correct 2 ms 4148 KB Ok
8 Correct 2 ms 4180 KB Ok
9 Correct 2 ms 4180 KB Ok
10 Correct 2 ms 4180 KB Ok
11 Correct 2 ms 4180 KB Ok
12 Correct 0 ms 212 KB Ok
13 Correct 2 ms 4180 KB Ok
14 Correct 2 ms 4180 KB Ok
15 Correct 3 ms 4152 KB Ok
16 Correct 2 ms 4180 KB Ok
17 Correct 2 ms 4180 KB Ok
18 Correct 16 ms 4280 KB Ok
19 Correct 256 ms 4880 KB Ok
20 Correct 44 ms 4400 KB Ok
21 Correct 522 ms 4864 KB Ok
22 Correct 92 ms 4560 KB Ok
23 Correct 2 ms 4180 KB Ok
24 Correct 2 ms 4180 KB Ok
25 Correct 2 ms 4180 KB Ok
26 Correct 2 ms 4156 KB Ok
27 Correct 2 ms 4180 KB Ok
28 Correct 2 ms 4148 KB Ok
29 Correct 2 ms 4180 KB Ok
30 Correct 2 ms 4180 KB Ok
31 Correct 3 ms 4180 KB Ok
32 Correct 3 ms 4180 KB Ok
33 Correct 2 ms 4180 KB Ok
34 Correct 4 ms 4180 KB Ok
35 Correct 4 ms 4268 KB Ok
36 Correct 3 ms 4280 KB Ok
37 Correct 3 ms 4180 KB Ok
38 Correct 4 ms 4180 KB Ok
39 Correct 3 ms 4264 KB Ok
40 Correct 3 ms 4180 KB Ok
41 Correct 4 ms 4180 KB Ok
42 Correct 4 ms 4180 KB Ok
43 Correct 3 ms 4180 KB Ok
44 Correct 6 ms 4308 KB Ok
45 Correct 7 ms 4308 KB Ok
46 Correct 8 ms 4308 KB Ok
47 Correct 6 ms 4308 KB Ok
48 Correct 6 ms 4308 KB Ok
49 Correct 6 ms 4308 KB Ok
50 Correct 7 ms 4376 KB Ok
51 Correct 6 ms 4308 KB Ok
52 Correct 6 ms 4308 KB Ok
53 Correct 6 ms 4404 KB Ok
54 Correct 46 ms 6956 KB Ok
55 Correct 61 ms 7460 KB Ok
56 Correct 55 ms 7372 KB Ok
57 Correct 38 ms 6344 KB Ok
58 Correct 55 ms 7004 KB Ok
59 Correct 48 ms 6752 KB Ok
60 Correct 46 ms 6516 KB Ok
61 Correct 40 ms 6476 KB Ok
62 Correct 64 ms 7372 KB Ok
63 Correct 44 ms 6656 KB Ok
64 Correct 59 ms 7356 KB Ok
65 Correct 54 ms 7164 KB Ok
66 Correct 45 ms 6732 KB Ok
67 Correct 36 ms 6536 KB Ok
68 Correct 51 ms 6892 KB Ok
69 Correct 765 ms 11220 KB Ok
70 Correct 311 ms 11580 KB Ok
71 Correct 449 ms 11628 KB Ok
72 Correct 310 ms 11044 KB Ok
73 Correct 620 ms 11468 KB Ok
74 Correct 300 ms 11588 KB Ok
75 Correct 240 ms 11332 KB Ok
76 Correct 377 ms 11204 KB Ok
77 Correct 863 ms 11532 KB Ok
78 Correct 558 ms 10932 KB Ok
79 Correct 625 ms 11396 KB Ok
80 Correct 354 ms 11568 KB Ok
81 Correct 172 ms 11440 KB Ok
82 Correct 990 ms 11528 KB Ok
83 Correct 617 ms 11572 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Ok
2 Correct 2 ms 4180 KB Ok
3 Correct 2 ms 4180 KB Ok
4 Correct 2 ms 4180 KB Ok
5 Correct 2 ms 4180 KB Ok
6 Correct 2 ms 4180 KB Ok
7 Correct 2 ms 4148 KB Ok
8 Correct 2 ms 4180 KB Ok
9 Correct 2 ms 4180 KB Ok
10 Correct 2 ms 4180 KB Ok
11 Correct 2 ms 4180 KB Ok
12 Correct 0 ms 212 KB Ok
13 Correct 2 ms 4180 KB Ok
14 Correct 2 ms 4180 KB Ok
15 Correct 3 ms 4152 KB Ok
16 Correct 2 ms 4180 KB Ok
17 Correct 2 ms 4180 KB Ok
18 Correct 16 ms 4280 KB Ok
19 Correct 256 ms 4880 KB Ok
20 Correct 44 ms 4400 KB Ok
21 Correct 522 ms 4864 KB Ok
22 Correct 92 ms 4560 KB Ok
23 Correct 2 ms 4180 KB Ok
24 Correct 2 ms 4180 KB Ok
25 Correct 2 ms 4180 KB Ok
26 Correct 2 ms 4156 KB Ok
27 Correct 2 ms 4180 KB Ok
28 Correct 2 ms 4148 KB Ok
29 Correct 2 ms 4180 KB Ok
30 Correct 2 ms 4180 KB Ok
31 Correct 3 ms 4180 KB Ok
32 Correct 3 ms 4180 KB Ok
33 Correct 2 ms 4180 KB Ok
34 Correct 2 ms 4180 KB Ok
35 Correct 2 ms 4124 KB Ok
36 Correct 3 ms 4152 KB Ok
37 Correct 2 ms 4180 KB Ok
38 Correct 3 ms 4180 KB Ok
39 Execution timed out 2077 ms 4376 KB Time limit exceeded
40 Halted 0 ms 0 KB -