oj.uz

Submission #701676

# Submission time Handle Problem Language Result Execution time Memory
701676 2023-02-21T23:06:54 Z angelo_torres Nice sequence (IZhO18_sequence) C++17
100 / 100
 1203 ms 84624 KB 
#include <bits/stdc++.h>
#define sz(v) (ll) v.size()
#define ff first
#define ss second

using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll N = 6e5 + 20;

ll sum(ll a,ll b){ return (a+b)%mod; }
ll mul(ll a,ll b){ return (a*b)%mod; }
ll res(ll a,ll b){ return (a-b+mod)%mod; }

int n,m,r[N];
vector<int> g[N];
bool c = 0;

void dfs(int v){
	r[v] = 1;
	for(auto u : g[v]){
		if(r[u] == 1) c = 1;
		if(!r[u]) dfs(u);
	}
	r[v] = 2;
}

bool go(int k){
	c = 0;
	for(int i = 0; i <= k; ++i){
		g[i].clear();
		r[i] = 0;
	} 
	for(int i = 0; i+n <= k; ++i){
		g[i].push_back(i+n);
	}
	for(int i = 0; i+m <= k; ++i){
		g[i+m].push_back(i);
	}
	for(int i = 0; i <= k; ++i){
		if(!r[i]) dfs(i);
	} 
	return c;
}

vector<ll> t;

void top(int v){
	r[v] = 1;
	for(auto u : g[v]){
		if(!r[u]) top(u);
	}
	t.push_back(v);
}

void solve(){
	cin >> n >> m;
	bool fl = (n < m);
	if(n > m) swap(n,m);
	// int L = 0, R = n+m-gcd(n,m)+2;
	// while(R-L > 1){
	// 	int md = (L+R)>>1;
	// 	if(go(md)) R = md;
	// 	else L = md;
	// }
	int L = n+m-gcd(n,m)-1;
	cout << L << endl;
	t.clear();
	for(int i  = 0; i <= L; ++i){
		g[i].clear();
		r[i] = 0; 
	} 
	for(int i = 0; i+n <= L; ++i){
		g[i].push_back(i+n);
	}
	for(int i = 0; i+m <= L; ++i){
		g[i+m].push_back(i);
	}
	for(int i = 0; i <= L; ++i){
		if(!r[i]) top(i);
	}
	vector<int> p(L+1);
	for(int i = 0; i <= L; ++i){
		p[t[i]] = i;
	}
	for(int i = 0; i+1 <= L; ++i){
		int ai = p[i+1]-p[i];
		cout << (fl ? ai : -ai) << " "; 
	}
	cout << endl;
}


int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int test; cin >> test;
	while(test--) solve();
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Ok
2 Correct 8 ms 14324 KB Ok
3 Correct 8 ms 14420 KB Ok
4 Correct 7 ms 14420 KB Ok
5 Correct 7 ms 14416 KB Ok
6 Correct 7 ms 14312 KB Ok
7 Correct 7 ms 14420 KB Ok
8 Correct 8 ms 14420 KB Ok
9 Correct 9 ms 14392 KB Ok
10 Correct 8 ms 14428 KB Ok
11 Correct 7 ms 14420 KB Ok
12 Correct 7 ms 14292 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Ok
2 Correct 9 ms 14420 KB Ok
3 Correct 7 ms 14424 KB Ok
4 Correct 8 ms 14420 KB Ok
5 Correct 9 ms 14420 KB Ok
6 Correct 9 ms 14544 KB Ok
7 Correct 17 ms 15564 KB Ok
8 Correct 12 ms 14932 KB Ok
9 Correct 17 ms 15828 KB Ok
10 Correct 14 ms 15188 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Ok
2 Correct 8 ms 14412 KB Ok
3 Correct 8 ms 14420 KB Ok
4 Correct 8 ms 14344 KB Ok
5 Correct 8 ms 14416 KB Ok
6 Correct 9 ms 14420 KB Ok
7 Correct 7 ms 14420 KB Ok
8 Correct 8 ms 14420 KB Ok
9 Correct 8 ms 14420 KB Ok
10 Correct 7 ms 14292 KB Ok
11 Correct 8 ms 14420 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Ok
2 Correct 9 ms 14420 KB Ok
3 Correct 8 ms 14420 KB Ok
4 Correct 8 ms 14420 KB Ok
5 Correct 9 ms 14420 KB Ok
6 Correct 85 ms 28728 KB Ok
7 Correct 79 ms 27460 KB Ok
8 Correct 141 ms 33524 KB Ok
9 Correct 106 ms 32088 KB Ok
10 Correct 63 ms 22976 KB Ok
11 Correct 101 ms 33040 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Ok
2 Correct 8 ms 14324 KB Ok
3 Correct 8 ms 14420 KB Ok
4 Correct 7 ms 14420 KB Ok
5 Correct 7 ms 14416 KB Ok
6 Correct 7 ms 14312 KB Ok
7 Correct 7 ms 14420 KB Ok
8 Correct 8 ms 14420 KB Ok
9 Correct 9 ms 14392 KB Ok
10 Correct 8 ms 14428 KB Ok
11 Correct 7 ms 14420 KB Ok
12 Correct 7 ms 14292 KB Ok
13 Correct 8 ms 14292 KB Ok
14 Correct 8 ms 14412 KB Ok
15 Correct 8 ms 14420 KB Ok
16 Correct 8 ms 14344 KB Ok
17 Correct 8 ms 14416 KB Ok
18 Correct 9 ms 14420 KB Ok
19 Correct 7 ms 14420 KB Ok
20 Correct 8 ms 14420 KB Ok
21 Correct 8 ms 14420 KB Ok
22 Correct 7 ms 14292 KB Ok
23 Correct 8 ms 14420 KB Ok
24 Correct 8 ms 14548 KB Ok
25 Correct 9 ms 14548 KB Ok
26 Correct 9 ms 14548 KB Ok
27 Correct 9 ms 14548 KB Ok
28 Correct 9 ms 14548 KB Ok
29 Correct 8 ms 14548 KB Ok
30 Correct 9 ms 14548 KB Ok
31 Correct 9 ms 14548 KB Ok
32 Correct 9 ms 14548 KB Ok
33 Correct 9 ms 14552 KB Ok
34 Correct 11 ms 14812 KB Ok
35 Correct 11 ms 14932 KB Ok
36 Correct 11 ms 14936 KB Ok
37 Correct 10 ms 14908 KB Ok
38 Correct 11 ms 14932 KB Ok
39 Correct 11 ms 14804 KB Ok
40 Correct 11 ms 14892 KB Ok
41 Correct 10 ms 14804 KB Ok
42 Correct 10 ms 14932 KB Ok
43 Correct 10 ms 14928 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Ok
2 Correct 8 ms 14324 KB Ok
3 Correct 8 ms 14420 KB Ok
4 Correct 7 ms 14420 KB Ok
5 Correct 7 ms 14416 KB Ok
6 Correct 7 ms 14312 KB Ok
7 Correct 7 ms 14420 KB Ok
8 Correct 8 ms 14420 KB Ok
9 Correct 9 ms 14392 KB Ok
10 Correct 8 ms 14428 KB Ok
11 Correct 7 ms 14420 KB Ok
12 Correct 7 ms 14292 KB Ok
13 Correct 8 ms 14420 KB Ok
14 Correct 9 ms 14420 KB Ok
15 Correct 7 ms 14424 KB Ok
16 Correct 8 ms 14420 KB Ok
17 Correct 9 ms 14420 KB Ok
18 Correct 9 ms 14544 KB Ok
19 Correct 17 ms 15564 KB Ok
20 Correct 12 ms 14932 KB Ok
21 Correct 17 ms 15828 KB Ok
22 Correct 14 ms 15188 KB Ok
23 Correct 8 ms 14292 KB Ok
24 Correct 8 ms 14412 KB Ok
25 Correct 8 ms 14420 KB Ok
26 Correct 8 ms 14344 KB Ok
27 Correct 8 ms 14416 KB Ok
28 Correct 9 ms 14420 KB Ok
29 Correct 7 ms 14420 KB Ok
30 Correct 8 ms 14420 KB Ok
31 Correct 8 ms 14420 KB Ok
32 Correct 7 ms 14292 KB Ok
33 Correct 8 ms 14420 KB Ok
34 Correct 8 ms 14548 KB Ok
35 Correct 9 ms 14548 KB Ok
36 Correct 9 ms 14548 KB Ok
37 Correct 9 ms 14548 KB Ok
38 Correct 9 ms 14548 KB Ok
39 Correct 8 ms 14548 KB Ok
40 Correct 9 ms 14548 KB Ok
41 Correct 9 ms 14548 KB Ok
42 Correct 9 ms 14548 KB Ok
43 Correct 9 ms 14552 KB Ok
44 Correct 11 ms 14812 KB Ok
45 Correct 11 ms 14932 KB Ok
46 Correct 11 ms 14936 KB Ok
47 Correct 10 ms 14908 KB Ok
48 Correct 11 ms 14932 KB Ok
49 Correct 11 ms 14804 KB Ok
50 Correct 11 ms 14892 KB Ok
51 Correct 10 ms 14804 KB Ok
52 Correct 10 ms 14932 KB Ok
53 Correct 10 ms 14928 KB Ok
54 Correct 76 ms 20688 KB Ok
55 Correct 76 ms 20968 KB Ok
56 Correct 73 ms 21108 KB Ok
57 Correct 68 ms 19896 KB Ok
58 Correct 66 ms 20340 KB Ok
59 Correct 65 ms 20024 KB Ok
60 Correct 58 ms 19644 KB Ok
61 Correct 58 ms 20176 KB Ok
62 Correct 74 ms 20544 KB Ok
63 Correct 61 ms 19908 KB Ok
64 Correct 75 ms 20688 KB Ok
65 Correct 69 ms 20552 KB Ok
66 Correct 64 ms 20368 KB Ok
67 Correct 57 ms 20176 KB Ok
68 Correct 66 ms 20424 KB Ok
69 Correct 170 ms 31164 KB Ok
70 Correct 181 ms 30548 KB Ok
71 Correct 167 ms 29416 KB Ok
72 Correct 158 ms 31164 KB Ok
73 Correct 165 ms 30140 KB Ok
74 Correct 172 ms 29828 KB Ok
75 Correct 149 ms 30528 KB Ok
76 Correct 197 ms 31288 KB Ok
77 Correct 170 ms 29172 KB Ok
78 Correct 180 ms 31332 KB Ok
79 Correct 179 ms 30016 KB Ok
80 Correct 160 ms 30780 KB Ok
81 Correct 163 ms 30912 KB Ok
82 Correct 168 ms 30140 KB Ok
83 Correct 166 ms 30740 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Ok
2 Correct 8 ms 14324 KB Ok
3 Correct 8 ms 14420 KB Ok
4 Correct 7 ms 14420 KB Ok
5 Correct 7 ms 14416 KB Ok
6 Correct 7 ms 14312 KB Ok
7 Correct 7 ms 14420 KB Ok
8 Correct 8 ms 14420 KB Ok
9 Correct 9 ms 14392 KB Ok
10 Correct 8 ms 14428 KB Ok
11 Correct 7 ms 14420 KB Ok
12 Correct 7 ms 14292 KB Ok
13 Correct 8 ms 14420 KB Ok
14 Correct 9 ms 14420 KB Ok
15 Correct 7 ms 14424 KB Ok
16 Correct 8 ms 14420 KB Ok
17 Correct 9 ms 14420 KB Ok
18 Correct 9 ms 14544 KB Ok
19 Correct 17 ms 15564 KB Ok
20 Correct 12 ms 14932 KB Ok
21 Correct 17 ms 15828 KB Ok
22 Correct 14 ms 15188 KB Ok
23 Correct 8 ms 14292 KB Ok
24 Correct 8 ms 14412 KB Ok
25 Correct 8 ms 14420 KB Ok
26 Correct 8 ms 14344 KB Ok
27 Correct 8 ms 14416 KB Ok
28 Correct 9 ms 14420 KB Ok
29 Correct 7 ms 14420 KB Ok
30 Correct 8 ms 14420 KB Ok
31 Correct 8 ms 14420 KB Ok
32 Correct 7 ms 14292 KB Ok
33 Correct 8 ms 14420 KB Ok
34 Correct 8 ms 14416 KB Ok
35 Correct 9 ms 14420 KB Ok
36 Correct 8 ms 14420 KB Ok
37 Correct 8 ms 14420 KB Ok
38 Correct 9 ms 14420 KB Ok
39 Correct 85 ms 28728 KB Ok
40 Correct 79 ms 27460 KB Ok
41 Correct 141 ms 33524 KB Ok
42 Correct 106 ms 32088 KB Ok
43 Correct 63 ms 22976 KB Ok
44 Correct 101 ms 33040 KB Ok
45 Correct 8 ms 14548 KB Ok
46 Correct 9 ms 14548 KB Ok
47 Correct 9 ms 14548 KB Ok
48 Correct 9 ms 14548 KB Ok
49 Correct 9 ms 14548 KB Ok
50 Correct 8 ms 14548 KB Ok
51 Correct 9 ms 14548 KB Ok
52 Correct 9 ms 14548 KB Ok
53 Correct 9 ms 14548 KB Ok
54 Correct 9 ms 14552 KB Ok
55 Correct 11 ms 14812 KB Ok
56 Correct 11 ms 14932 KB Ok
57 Correct 11 ms 14936 KB Ok
58 Correct 10 ms 14908 KB Ok
59 Correct 11 ms 14932 KB Ok
60 Correct 11 ms 14804 KB Ok
61 Correct 11 ms 14892 KB Ok
62 Correct 10 ms 14804 KB Ok
63 Correct 10 ms 14932 KB Ok
64 Correct 10 ms 14928 KB Ok
65 Correct 76 ms 20688 KB Ok
66 Correct 76 ms 20968 KB Ok
67 Correct 73 ms 21108 KB Ok
68 Correct 68 ms 19896 KB Ok
69 Correct 66 ms 20340 KB Ok
70 Correct 65 ms 20024 KB Ok
71 Correct 58 ms 19644 KB Ok
72 Correct 58 ms 20176 KB Ok
73 Correct 74 ms 20544 KB Ok
74 Correct 61 ms 19908 KB Ok
75 Correct 75 ms 20688 KB Ok
76 Correct 69 ms 20552 KB Ok
77 Correct 64 ms 20368 KB Ok
78 Correct 57 ms 20176 KB Ok
79 Correct 66 ms 20424 KB Ok
80 Correct 170 ms 31164 KB Ok
81 Correct 181 ms 30548 KB Ok
82 Correct 167 ms 29416 KB Ok
83 Correct 158 ms 31164 KB Ok
84 Correct 165 ms 30140 KB Ok
85 Correct 172 ms 29828 KB Ok
86 Correct 149 ms 30528 KB Ok
87 Correct 197 ms 31288 KB Ok
88 Correct 170 ms 29172 KB Ok
89 Correct 180 ms 31332 KB Ok
90 Correct 179 ms 30016 KB Ok
91 Correct 160 ms 30780 KB Ok
92 Correct 163 ms 30912 KB Ok
93 Correct 168 ms 30140 KB Ok
94 Correct 166 ms 30740 KB Ok
95 Correct 159 ms 30876 KB Ok
96 Correct 224 ms 38196 KB Ok
97 Correct 224 ms 33880 KB Ok
98 Correct 170 ms 33848 KB Ok
99 Correct 195 ms 33072 KB Ok
100 Correct 201 ms 32752 KB Ok
101 Correct 209 ms 35836 KB Ok
102 Correct 201 ms 34104 KB Ok
103 Correct 207 ms 35632 KB Ok
104 Correct 237 ms 36912 KB Ok
105 Correct 242 ms 37820 KB Ok
106 Correct 197 ms 37920 KB Ok
107 Correct 211 ms 36132 KB Ok
108 Correct 233 ms 36948 KB Ok
109 Correct 216 ms 39032 KB Ok
110 Correct 968 ms 83656 KB Ok
111 Correct 1101 ms 84452 KB Ok
112 Correct 1103 ms 74336 KB Ok
113 Correct 1038 ms 83684 KB Ok
114 Correct 1147 ms 83692 KB Ok
115 Correct 1141 ms 83036 KB Ok
116 Correct 1171 ms 82788 KB Ok
117 Correct 1065 ms 84120 KB Ok
118 Correct 1042 ms 77724 KB Ok
119 Correct 1128 ms 83252 KB Ok
120 Correct 1136 ms 83776 KB Ok
121 Correct 1115 ms 84624 KB Ok
122 Correct 1062 ms 80048 KB Ok
123 Correct 1203 ms 83752 KB Ok
124 Correct 1014 ms 74268 KB Ok
125 Correct 348 ms 43224 KB Ok