oj.uz

Submission #789556

# Submission time Handle Problem Language Result Execution time Memory
789556 2023-07-21T13:37:47 Z temporary_juggernaut Nice sequence (IZhO18_sequence) C++14
100 / 100
 302 ms 41640 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n, m;
int timer, len;
bool used[800005];
int pref[400005];
void dfs(int v){
	used[v] = true;
	{
		int to = v - m;
		if(to >= 0 && !used[to])
			dfs(to);
	}
	{
		int to = v + n;
		if(to <= len && !used[to])
			dfs(to);
	}
	pref[v] = timer++;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tests;
  	cin >> tests;
	while(tests--){
		cin >> n >> m;
		timer = 0;
		len = n + m - __gcd(n, m) - 1;
		fill(used, used + len + 1, false);
		for(int i = 0; i <= len; i++)
			if(!used[i])
				dfs(i);
		cout << len << '\n';
		fill(used, used + len + 1, false);
		if(len){
			for(int i = 1; i <= len; i++)
				cout << pref[i] - pref[i - 1] << ' ';
			cout << '\n';
		}
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 328 KB Ok
12 Correct 1 ms 340 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 340 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 2 ms 340 KB Ok
7 Correct 5 ms 852 KB Ok
8 Correct 3 ms 596 KB Ok
9 Correct 6 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 1 ms 328 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 1 ms 340 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 1 ms 212 KB Ok
11 Correct 1 ms 340 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 46 ms 6352 KB Ok
7 Correct 42 ms 9584 KB Ok
8 Correct 81 ms 12512 KB Ok
9 Correct 61 ms 11024 KB Ok
10 Correct 33 ms 4812 KB Ok
11 Correct 56 ms 7732 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 328 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 328 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 0 ms 212 KB Ok
16 Correct 0 ms 212 KB Ok
17 Correct 1 ms 340 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 1 ms 212 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 1 ms 340 KB Ok
25 Correct 2 ms 340 KB Ok
26 Correct 1 ms 340 KB Ok
27 Correct 1 ms 336 KB Ok
28 Correct 1 ms 328 KB Ok
29 Correct 1 ms 340 KB Ok
30 Correct 1 ms 324 KB Ok
31 Correct 1 ms 340 KB Ok
32 Correct 2 ms 328 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 3 ms 468 KB Ok
35 Correct 3 ms 596 KB Ok
36 Correct 3 ms 580 KB Ok
37 Correct 3 ms 476 KB Ok
38 Correct 2 ms 596 KB Ok
39 Correct 2 ms 468 KB Ok
40 Correct 3 ms 596 KB Ok
41 Correct 2 ms 596 KB Ok
42 Correct 3 ms 468 KB Ok
43 Correct 3 ms 596 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 328 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 1 ms 340 KB Ok
15 Correct 0 ms 212 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 2 ms 340 KB Ok
19 Correct 5 ms 852 KB Ok
20 Correct 3 ms 596 KB Ok
21 Correct 6 ms 940 KB Ok
22 Correct 4 ms 724 KB Ok
23 Correct 1 ms 328 KB Ok
24 Correct 0 ms 340 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 1 ms 340 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 1 ms 212 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 1 ms 340 KB Ok
35 Correct 2 ms 340 KB Ok
36 Correct 1 ms 340 KB Ok
37 Correct 1 ms 336 KB Ok
38 Correct 1 ms 328 KB Ok
39 Correct 1 ms 340 KB Ok
40 Correct 1 ms 324 KB Ok
41 Correct 1 ms 340 KB Ok
42 Correct 2 ms 328 KB Ok
43 Correct 1 ms 340 KB Ok
44 Correct 3 ms 468 KB Ok
45 Correct 3 ms 596 KB Ok
46 Correct 3 ms 580 KB Ok
47 Correct 3 ms 476 KB Ok
48 Correct 2 ms 596 KB Ok
49 Correct 2 ms 468 KB Ok
50 Correct 3 ms 596 KB Ok
51 Correct 2 ms 596 KB Ok
52 Correct 3 ms 468 KB Ok
53 Correct 3 ms 596 KB Ok
54 Correct 40 ms 2456 KB Ok
55 Correct 41 ms 2692 KB Ok
56 Correct 40 ms 2764 KB Ok
57 Correct 31 ms 2060 KB Ok
58 Correct 36 ms 2232 KB Ok
59 Correct 34 ms 2064 KB Ok
60 Correct 30 ms 1856 KB Ok
61 Correct 30 ms 2048 KB Ok
62 Correct 40 ms 2448 KB Ok
63 Correct 34 ms 2132 KB Ok
64 Correct 41 ms 2724 KB Ok
65 Correct 37 ms 2288 KB Ok
66 Correct 34 ms 2120 KB Ok
67 Correct 32 ms 2092 KB Ok
68 Correct 38 ms 2252 KB Ok
69 Correct 64 ms 9684 KB Ok
70 Correct 67 ms 10300 KB Ok
71 Correct 69 ms 9804 KB Ok
72 Correct 62 ms 9716 KB Ok
73 Correct 63 ms 9308 KB Ok
74 Correct 72 ms 9080 KB Ok
75 Correct 62 ms 9060 KB Ok
76 Correct 64 ms 9936 KB Ok
77 Correct 64 ms 8732 KB Ok
78 Correct 64 ms 9040 KB Ok
79 Correct 66 ms 9676 KB Ok
80 Correct 63 ms 9796 KB Ok
81 Correct 79 ms 9288 KB Ok
82 Correct 62 ms 9524 KB Ok
83 Correct 66 ms 9136 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 328 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 1 ms 340 KB Ok
15 Correct 0 ms 212 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 2 ms 340 KB Ok
19 Correct 5 ms 852 KB Ok
20 Correct 3 ms 596 KB Ok
21 Correct 6 ms 940 KB Ok
22 Correct 4 ms 724 KB Ok
23 Correct 1 ms 328 KB Ok
24 Correct 0 ms 340 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 1 ms 340 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 1 ms 212 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 1 ms 332 KB Ok
35 Correct 1 ms 212 KB Ok
36 Correct 1 ms 212 KB Ok
37 Correct 1 ms 340 KB Ok
38 Correct 1 ms 340 KB Ok
39 Correct 46 ms 6352 KB Ok
40 Correct 42 ms 9584 KB Ok
41 Correct 81 ms 12512 KB Ok
42 Correct 61 ms 11024 KB Ok
43 Correct 33 ms 4812 KB Ok
44 Correct 56 ms 7732 KB Ok
45 Correct 1 ms 340 KB Ok
46 Correct 2 ms 340 KB Ok
47 Correct 1 ms 340 KB Ok
48 Correct 1 ms 336 KB Ok
49 Correct 1 ms 328 KB Ok
50 Correct 1 ms 340 KB Ok
51 Correct 1 ms 324 KB Ok
52 Correct 1 ms 340 KB Ok
53 Correct 2 ms 328 KB Ok
54 Correct 1 ms 340 KB Ok
55 Correct 3 ms 468 KB Ok
56 Correct 3 ms 596 KB Ok
57 Correct 3 ms 580 KB Ok
58 Correct 3 ms 476 KB Ok
59 Correct 2 ms 596 KB Ok
60 Correct 2 ms 468 KB Ok
61 Correct 3 ms 596 KB Ok
62 Correct 2 ms 596 KB Ok
63 Correct 3 ms 468 KB Ok
64 Correct 3 ms 596 KB Ok
65 Correct 40 ms 2456 KB Ok
66 Correct 41 ms 2692 KB Ok
67 Correct 40 ms 2764 KB Ok
68 Correct 31 ms 2060 KB Ok
69 Correct 36 ms 2232 KB Ok
70 Correct 34 ms 2064 KB Ok
71 Correct 30 ms 1856 KB Ok
72 Correct 30 ms 2048 KB Ok
73 Correct 40 ms 2448 KB Ok
74 Correct 34 ms 2132 KB Ok
75 Correct 41 ms 2724 KB Ok
76 Correct 37 ms 2288 KB Ok
77 Correct 34 ms 2120 KB Ok
78 Correct 32 ms 2092 KB Ok
79 Correct 38 ms 2252 KB Ok
80 Correct 64 ms 9684 KB Ok
81 Correct 67 ms 10300 KB Ok
82 Correct 69 ms 9804 KB Ok
83 Correct 62 ms 9716 KB Ok
84 Correct 63 ms 9308 KB Ok
85 Correct 72 ms 9080 KB Ok
86 Correct 62 ms 9060 KB Ok
87 Correct 64 ms 9936 KB Ok
88 Correct 64 ms 8732 KB Ok
89 Correct 64 ms 9040 KB Ok
90 Correct 66 ms 9676 KB Ok
91 Correct 63 ms 9796 KB Ok
92 Correct 79 ms 9288 KB Ok
93 Correct 62 ms 9524 KB Ok
94 Correct 66 ms 9136 KB Ok
95 Correct 86 ms 5660 KB Ok
96 Correct 129 ms 7644 KB Ok
97 Correct 123 ms 6824 KB Ok
98 Correct 111 ms 5752 KB Ok
99 Correct 113 ms 6340 KB Ok
100 Correct 112 ms 6480 KB Ok
101 Correct 114 ms 6752 KB Ok
102 Correct 113 ms 6708 KB Ok
103 Correct 108 ms 6688 KB Ok
104 Correct 137 ms 7884 KB Ok
105 Correct 129 ms 7500 KB Ok
106 Correct 134 ms 7196 KB Ok
107 Correct 118 ms 7124 KB Ok
108 Correct 128 ms 7892 KB Ok
109 Correct 118 ms 7756 KB Ok
110 Correct 302 ms 38948 KB Ok
111 Correct 277 ms 41216 KB Ok
112 Correct 277 ms 38488 KB Ok
113 Correct 268 ms 41416 KB Ok
114 Correct 288 ms 41640 KB Ok
115 Correct 265 ms 39092 KB Ok
116 Correct 272 ms 41380 KB Ok
117 Correct 285 ms 40472 KB Ok
118 Correct 262 ms 40908 KB Ok
119 Correct 255 ms 40040 KB Ok
120 Correct 260 ms 39980 KB Ok
121 Correct 263 ms 39500 KB Ok
122 Correct 268 ms 40004 KB Ok
123 Correct 275 ms 41388 KB Ok
124 Correct 257 ms 36620 KB Ok
125 Correct 229 ms 24860 KB Ok