oj.uz

Submission #797335

# Submission time Handle Problem Language Result Execution time Memory
797335 2023-07-29T09:27:57 Z kingfran1907 Nice sequence (IZhO18_sequence) C++14
61 / 100
 2000 ms 8116 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;
		}
		
		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++) 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 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 0 ms 212 KB Ok
8 Correct 1 ms 284 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 0 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 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 14 ms 376 KB Ok
7 Correct 253 ms 816 KB Ok
8 Correct 42 ms 504 KB Ok
9 Correct 519 ms 972 KB Ok
10 Correct 92 ms 588 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 1 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 0 ms 212 KB Ok
7 Correct 0 ms 212 KB Ok
8 Correct 0 ms 212 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 0 ms 212 KB Ok
11 Correct 0 ms 212 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Execution timed out 2066 ms 1232 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
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 0 ms 212 KB Ok
8 Correct 1 ms 284 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 0 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 1 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 0 ms 212 KB Ok
19 Correct 0 ms 212 KB Ok
20 Correct 0 ms 212 KB Ok
21 Correct 0 ms 212 KB Ok
22 Correct 0 ms 212 KB Ok
23 Correct 0 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 2 ms 340 KB Ok
28 Correct 1 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 4 ms 468 KB Ok
35 Correct 4 ms 468 KB Ok
36 Correct 6 ms 500 KB Ok
37 Correct 4 ms 468 KB Ok
38 Correct 4 ms 468 KB Ok
39 Correct 3 ms 468 KB Ok
40 Correct 5 ms 492 KB Ok
41 Correct 4 ms 468 KB Ok
42 Correct 4 ms 468 KB Ok
43 Correct 4 ms 492 KB Ok

Subtask #6
18.0 / 18.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 0 ms 212 KB Ok
8 Correct 1 ms 284 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 0 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 14 ms 376 KB Ok
19 Correct 253 ms 816 KB Ok
20 Correct 42 ms 504 KB Ok
21 Correct 519 ms 972 KB Ok
22 Correct 92 ms 588 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 1 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 0 ms 212 KB Ok
29 Correct 0 ms 212 KB Ok
30 Correct 0 ms 212 KB Ok
31 Correct 0 ms 212 KB Ok
32 Correct 0 ms 212 KB Ok
33 Correct 0 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 2 ms 340 KB Ok
38 Correct 1 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 4 ms 468 KB Ok
45 Correct 4 ms 468 KB Ok
46 Correct 6 ms 500 KB Ok
47 Correct 4 ms 468 KB Ok
48 Correct 4 ms 468 KB Ok
49 Correct 3 ms 468 KB Ok
50 Correct 5 ms 492 KB Ok
51 Correct 4 ms 468 KB Ok
52 Correct 4 ms 468 KB Ok
53 Correct 4 ms 492 KB Ok
54 Correct 48 ms 3412 KB Ok
55 Correct 58 ms 3916 KB Ok
56 Correct 53 ms 3888 KB Ok
57 Correct 37 ms 2796 KB Ok
58 Correct 57 ms 3452 KB Ok
59 Correct 51 ms 3248 KB Ok
60 Correct 38 ms 2816 KB Ok
61 Correct 39 ms 2992 KB Ok
62 Correct 64 ms 3868 KB Ok
63 Correct 43 ms 3068 KB Ok
64 Correct 61 ms 3860 KB Ok
65 Correct 53 ms 3640 KB Ok
66 Correct 43 ms 3152 KB Ok
67 Correct 34 ms 2892 KB Ok
68 Correct 50 ms 3304 KB Ok
69 Correct 759 ms 7804 KB Ok
70 Correct 317 ms 8012 KB Ok
71 Correct 444 ms 8116 KB Ok
72 Correct 317 ms 7516 KB Ok
73 Correct 626 ms 7976 KB Ok
74 Correct 303 ms 7980 KB Ok
75 Correct 245 ms 7756 KB Ok
76 Correct 350 ms 7664 KB Ok
77 Correct 849 ms 8048 KB Ok
78 Correct 608 ms 7500 KB Ok
79 Correct 610 ms 7884 KB Ok
80 Correct 332 ms 8068 KB Ok
81 Correct 168 ms 7884 KB Ok
82 Correct 986 ms 8020 KB Ok
83 Correct 620 ms 8004 KB Ok

Subtask #7
0 / 24.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 0 ms 212 KB Ok
8 Correct 1 ms 284 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 0 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 14 ms 376 KB Ok
19 Correct 253 ms 816 KB Ok
20 Correct 42 ms 504 KB Ok
21 Correct 519 ms 972 KB Ok
22 Correct 92 ms 588 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 1 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 0 ms 212 KB Ok
29 Correct 0 ms 212 KB Ok
30 Correct 0 ms 212 KB Ok
31 Correct 0 ms 212 KB Ok
32 Correct 0 ms 212 KB Ok
33 Correct 0 ms 212 KB Ok
34 Correct 0 ms 212 KB Ok
35 Correct 1 ms 212 KB Ok
36 Correct 0 ms 212 KB Ok
37 Correct 1 ms 212 KB Ok
38 Correct 0 ms 212 KB Ok
39 Execution timed out 2066 ms 1232 KB Time limit exceeded
40 Halted 0 ms 0 KB -