oj.uz

Submission #1116153

# Submission time Handle Problem Language Result Execution time Memory
1116153 2024-11-21T09:38:18 Z adiyer Nice sequence (IZhO18_sequence) C++17
100 / 100
 982 ms 91328 KB 
#include <bits/stdc++.h>

using namespace std;

typedef int ll;

const int N = 1e6 + 11;

// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

ll n, m, pos;
ll a[N], was[N], ans[N];

vector < ll > ord, g[N];

bool cyc;

void dfs(ll v){
	was[v] = 1;
	for(ll u : g[v])
		if(!was[u])
			dfs(u);
	ord.push_back(v);
}

bool f(ll sz){
	cyc = 0, ord.clear();
	fill(was, was + sz + 1, 0);
	for(ll i = 0; i <= sz; i++){
		g[i].clear();
		if(i - n >= 0) g[i].push_back(i - n);
		if(i + m <= sz) g[i].push_back(i + m);
	}
	for(ll i = 0; i <= sz; i++)
		if(!was[i])
			dfs(i);
	reverse(ord.begin(), ord.end());
	fill(was, was + sz + 1, 0);
	for(ll v : ord){
		was[v] = 1;
		for(ll u : g[v]){
			if(was[u]){
				return 0;
			}
		}
	}
	return 1;
}

void solve(){
	cin >> n >> m;
	ll l = n + m - 1 - gcd(n, m);
	fill(ans, ans + l + 1, 0), f(l);
	for(ll i = 0; i <= l; i++) ans[ord[i]] = i + 1;
	ll p = ans[0];
	cout << l << '\n';
	for(ll i = 1; i <= l; i++) cout << ans[i] - p << ' ', p += ans[i] - p;
	cout << '\n';
}

signed main(){
	ll cs;
	cin >> cs;
	while(cs--){
		solve();
	}
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27216 KB Ok
2 Correct 6 ms 27384 KB Ok
3 Correct 5 ms 27216 KB Ok
4 Correct 6 ms 27232 KB Ok
5 Correct 6 ms 27216 KB Ok
6 Correct 7 ms 27472 KB Ok
7 Correct 11 ms 28240 KB Ok
8 Correct 9 ms 27472 KB Ok
9 Correct 13 ms 28240 KB Ok
10 Correct 10 ms 27728 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27216 KB Ok
2 Correct 5 ms 27216 KB Ok
3 Correct 5 ms 27216 KB Ok
4 Correct 8 ms 27216 KB Ok
5 Correct 5 ms 27228 KB Ok
6 Correct 75 ms 43696 KB Ok
7 Correct 67 ms 43200 KB Ok
8 Correct 109 ms 46272 KB Ok
9 Correct 93 ms 42692 KB Ok
10 Correct 57 ms 38336 KB Ok
11 Correct 90 ms 48076 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27216 KB Ok
2 Correct 5 ms 27216 KB Ok
3 Correct 5 ms 27216 KB Ok
4 Correct 5 ms 27216 KB Ok
5 Correct 5 ms 27216 KB Ok
6 Correct 5 ms 27216 KB Ok
7 Correct 5 ms 27216 KB Ok
8 Correct 6 ms 27216 KB Ok
9 Correct 5 ms 27388 KB Ok
10 Correct 5 ms 27384 KB Ok
11 Correct 5 ms 27216 KB Ok
12 Correct 5 ms 27216 KB Ok
13 Correct 5 ms 27216 KB Ok
14 Correct 4 ms 27256 KB Ok
15 Correct 5 ms 27216 KB Ok
16 Correct 7 ms 27216 KB Ok
17 Correct 5 ms 27216 KB Ok
18 Correct 5 ms 27216 KB Ok
19 Correct 5 ms 27216 KB Ok
20 Correct 6 ms 27216 KB Ok
21 Correct 5 ms 27216 KB Ok
22 Correct 5 ms 27216 KB Ok
23 Correct 6 ms 27216 KB Ok
24 Correct 6 ms 27216 KB Ok
25 Correct 6 ms 27472 KB Ok
26 Correct 7 ms 27388 KB Ok
27 Correct 6 ms 27472 KB Ok
28 Correct 7 ms 27216 KB Ok
29 Correct 7 ms 27384 KB Ok
30 Correct 6 ms 27264 KB Ok
31 Correct 6 ms 27216 KB Ok
32 Correct 6 ms 27272 KB Ok
33 Correct 6 ms 27216 KB Ok
34 Correct 8 ms 27472 KB Ok
35 Correct 8 ms 27472 KB Ok
36 Correct 9 ms 27520 KB Ok
37 Correct 10 ms 27728 KB Ok
38 Correct 8 ms 27516 KB Ok
39 Correct 8 ms 27472 KB Ok
40 Correct 8 ms 27728 KB Ok
41 Correct 8 ms 27728 KB Ok
42 Correct 9 ms 27728 KB Ok
43 Correct 8 ms 27728 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27216 KB Ok
2 Correct 5 ms 27216 KB Ok
3 Correct 5 ms 27216 KB Ok
4 Correct 5 ms 27216 KB Ok
5 Correct 5 ms 27216 KB Ok
6 Correct 5 ms 27216 KB Ok
7 Correct 5 ms 27216 KB Ok
8 Correct 6 ms 27216 KB Ok
9 Correct 5 ms 27388 KB Ok
10 Correct 5 ms 27384 KB Ok
11 Correct 5 ms 27216 KB Ok
12 Correct 5 ms 27216 KB Ok
13 Correct 7 ms 27216 KB Ok
14 Correct 6 ms 27384 KB Ok
15 Correct 5 ms 27216 KB Ok
16 Correct 6 ms 27232 KB Ok
17 Correct 6 ms 27216 KB Ok
18 Correct 7 ms 27472 KB Ok
19 Correct 11 ms 28240 KB Ok
20 Correct 9 ms 27472 KB Ok
21 Correct 13 ms 28240 KB Ok
22 Correct 10 ms 27728 KB Ok
23 Correct 5 ms 27216 KB Ok
24 Correct 4 ms 27256 KB Ok
25 Correct 5 ms 27216 KB Ok
26 Correct 7 ms 27216 KB Ok
27 Correct 5 ms 27216 KB Ok
28 Correct 5 ms 27216 KB Ok
29 Correct 5 ms 27216 KB Ok
30 Correct 6 ms 27216 KB Ok
31 Correct 5 ms 27216 KB Ok
32 Correct 5 ms 27216 KB Ok
33 Correct 6 ms 27216 KB Ok
34 Correct 6 ms 27216 KB Ok
35 Correct 6 ms 27472 KB Ok
36 Correct 7 ms 27388 KB Ok
37 Correct 6 ms 27472 KB Ok
38 Correct 7 ms 27216 KB Ok
39 Correct 7 ms 27384 KB Ok
40 Correct 6 ms 27264 KB Ok
41 Correct 6 ms 27216 KB Ok
42 Correct 6 ms 27272 KB Ok
43 Correct 6 ms 27216 KB Ok
44 Correct 8 ms 27472 KB Ok
45 Correct 8 ms 27472 KB Ok
46 Correct 9 ms 27520 KB Ok
47 Correct 10 ms 27728 KB Ok
48 Correct 8 ms 27516 KB Ok
49 Correct 8 ms 27472 KB Ok
50 Correct 8 ms 27728 KB Ok
51 Correct 8 ms 27728 KB Ok
52 Correct 9 ms 27728 KB Ok
53 Correct 8 ms 27728 KB Ok
54 Correct 54 ms 32464 KB Ok
55 Correct 62 ms 32872 KB Ok
56 Correct 66 ms 32960 KB Ok
57 Correct 48 ms 31892 KB Ok
58 Correct 61 ms 32720 KB Ok
59 Correct 73 ms 32448 KB Ok
60 Correct 48 ms 31936 KB Ok
61 Correct 48 ms 32192 KB Ok
62 Correct 108 ms 33240 KB Ok
63 Correct 57 ms 32192 KB Ok
64 Correct 100 ms 32960 KB Ok
65 Correct 63 ms 32756 KB Ok
66 Correct 65 ms 32448 KB Ok
67 Correct 54 ms 32096 KB Ok
68 Correct 56 ms 32824 KB Ok
69 Correct 126 ms 41404 KB Ok
70 Correct 135 ms 41412 KB Ok
71 Correct 125 ms 39364 KB Ok
72 Correct 137 ms 41380 KB Ok
73 Correct 129 ms 39492 KB Ok
74 Correct 124 ms 40412 KB Ok
75 Correct 133 ms 41160 KB Ok
76 Correct 127 ms 41296 KB Ok
77 Correct 124 ms 40204 KB Ok
78 Correct 160 ms 41356 KB Ok
79 Correct 121 ms 40648 KB Ok
80 Correct 147 ms 39372 KB Ok
81 Correct 122 ms 41412 KB Ok
82 Correct 148 ms 40548 KB Ok
83 Correct 148 ms 41412 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27216 KB Ok
2 Correct 5 ms 27216 KB Ok
3 Correct 5 ms 27216 KB Ok
4 Correct 5 ms 27216 KB Ok
5 Correct 5 ms 27216 KB Ok
6 Correct 5 ms 27216 KB Ok
7 Correct 5 ms 27216 KB Ok
8 Correct 6 ms 27216 KB Ok
9 Correct 5 ms 27388 KB Ok
10 Correct 5 ms 27384 KB Ok
11 Correct 5 ms 27216 KB Ok
12 Correct 5 ms 27216 KB Ok
13 Correct 7 ms 27216 KB Ok
14 Correct 6 ms 27384 KB Ok
15 Correct 5 ms 27216 KB Ok
16 Correct 6 ms 27232 KB Ok
17 Correct 6 ms 27216 KB Ok
18 Correct 7 ms 27472 KB Ok
19 Correct 11 ms 28240 KB Ok
20 Correct 9 ms 27472 KB Ok
21 Correct 13 ms 28240 KB Ok
22 Correct 10 ms 27728 KB Ok
23 Correct 5 ms 27216 KB Ok
24 Correct 4 ms 27256 KB Ok
25 Correct 5 ms 27216 KB Ok
26 Correct 7 ms 27216 KB Ok
27 Correct 5 ms 27216 KB Ok
28 Correct 5 ms 27216 KB Ok
29 Correct 5 ms 27216 KB Ok
30 Correct 6 ms 27216 KB Ok
31 Correct 5 ms 27216 KB Ok
32 Correct 5 ms 27216 KB Ok
33 Correct 6 ms 27216 KB Ok
34 Correct 5 ms 27216 KB Ok
35 Correct 5 ms 27216 KB Ok
36 Correct 5 ms 27216 KB Ok
37 Correct 8 ms 27216 KB Ok
38 Correct 5 ms 27228 KB Ok
39 Correct 75 ms 43696 KB Ok
40 Correct 67 ms 43200 KB Ok
41 Correct 109 ms 46272 KB Ok
42 Correct 93 ms 42692 KB Ok
43 Correct 57 ms 38336 KB Ok
44 Correct 90 ms 48076 KB Ok
45 Correct 6 ms 27216 KB Ok
46 Correct 6 ms 27472 KB Ok
47 Correct 7 ms 27388 KB Ok
48 Correct 6 ms 27472 KB Ok
49 Correct 7 ms 27216 KB Ok
50 Correct 7 ms 27384 KB Ok
51 Correct 6 ms 27264 KB Ok
52 Correct 6 ms 27216 KB Ok
53 Correct 6 ms 27272 KB Ok
54 Correct 6 ms 27216 KB Ok
55 Correct 8 ms 27472 KB Ok
56 Correct 8 ms 27472 KB Ok
57 Correct 9 ms 27520 KB Ok
58 Correct 10 ms 27728 KB Ok
59 Correct 8 ms 27516 KB Ok
60 Correct 8 ms 27472 KB Ok
61 Correct 8 ms 27728 KB Ok
62 Correct 8 ms 27728 KB Ok
63 Correct 9 ms 27728 KB Ok
64 Correct 8 ms 27728 KB Ok
65 Correct 54 ms 32464 KB Ok
66 Correct 62 ms 32872 KB Ok
67 Correct 66 ms 32960 KB Ok
68 Correct 48 ms 31892 KB Ok
69 Correct 61 ms 32720 KB Ok
70 Correct 73 ms 32448 KB Ok
71 Correct 48 ms 31936 KB Ok
72 Correct 48 ms 32192 KB Ok
73 Correct 108 ms 33240 KB Ok
74 Correct 57 ms 32192 KB Ok
75 Correct 100 ms 32960 KB Ok
76 Correct 63 ms 32756 KB Ok
77 Correct 65 ms 32448 KB Ok
78 Correct 54 ms 32096 KB Ok
79 Correct 56 ms 32824 KB Ok
80 Correct 126 ms 41404 KB Ok
81 Correct 135 ms 41412 KB Ok
82 Correct 125 ms 39364 KB Ok
83 Correct 137 ms 41380 KB Ok
84 Correct 129 ms 39492 KB Ok
85 Correct 124 ms 40412 KB Ok
86 Correct 133 ms 41160 KB Ok
87 Correct 127 ms 41296 KB Ok
88 Correct 124 ms 40204 KB Ok
89 Correct 160 ms 41356 KB Ok
90 Correct 121 ms 40648 KB Ok
91 Correct 147 ms 39372 KB Ok
92 Correct 122 ms 41412 KB Ok
93 Correct 148 ms 40548 KB Ok
94 Correct 148 ms 41412 KB Ok
95 Correct 126 ms 41412 KB Ok
96 Correct 191 ms 50936 KB Ok
97 Correct 178 ms 45668 KB Ok
98 Correct 141 ms 44856 KB Ok
99 Correct 182 ms 44972 KB Ok
100 Correct 194 ms 45244 KB Ok
101 Correct 187 ms 46776 KB Ok
102 Correct 163 ms 45752 KB Ok
103 Correct 195 ms 46704 KB Ok
104 Correct 186 ms 48056 KB Ok
105 Correct 196 ms 50360 KB Ok
106 Correct 168 ms 49336 KB Ok
107 Correct 179 ms 47288 KB Ok
108 Correct 241 ms 50868 KB Ok
109 Correct 200 ms 50620 KB Ok
110 Correct 782 ms 90552 KB Ok
111 Correct 777 ms 91328 KB Ok
112 Correct 900 ms 84700 KB Ok
113 Correct 619 ms 90300 KB Ok
114 Correct 831 ms 83332 KB Ok
115 Correct 968 ms 91312 KB Ok
116 Correct 982 ms 90204 KB Ok
117 Correct 885 ms 91144 KB Ok
118 Correct 756 ms 81876 KB Ok
119 Correct 840 ms 90252 KB Ok
120 Correct 904 ms 91156 KB Ok
121 Correct 787 ms 87868 KB Ok
122 Correct 708 ms 90816 KB Ok
123 Correct 920 ms 87844 KB Ok
124 Correct 643 ms 83908 KB Ok
125 Correct 327 ms 74692 KB Ok