oj.uz

Submission #634984

# Submission time Handle Problem Language Result Execution time Memory
634984 2022-08-25T09:55:50 Z drkarlicio2107 Nice sequence (IZhO18_sequence) C++14
76 / 100
 1553 ms 40840 KB 
#include <bits/stdc++.h>
using namespace std;
int vis [400010];  long long int  c=0; long long int n, m;
vector < int > g [400010];
vector < long long int > ans;
long long int  o [400010];
int vis2 [400010];
int vis3 [400010];
void dfs ( int  x,  long long int  d){
	if (vis [x]) return ;
	vis [x]=1;
	if (x+n<=d){
		g [x+n].push_back (x); //dfs (x+n, d); 
	}
	if (x+m<=d){
		g [x].push_back (x+m); dfs (x+m, d);
	}
	return ;
}
void dfs2 ( int  v) {
    vis2[v]=1;
    for ( long long int  u : g[v]) {
        if (!vis2[u]) dfs2(u);
    }
    ans.push_back(v);
    return ;
}

void is_cycle ( long long int  x) {
	if (vis3 [x]==1){
		c=1; return ;
	}
	if (vis3 [x]) return ;
	vis3 [x]=1;
	for ( long long int  u : g[x]) is_cycle (u);
	vis3 [x]=2;
	return ;
}

void sort_top( long long int  d) {
    memset (vis2, 0, sizeof vis2); ans.clear();
    for ( long long int  i=0; i<=d; i++) {
        if (!vis2[i])
            dfs2(i);
    }
    reverse(ans.begin(), ans.end());
    return ;
}
 long long int  ok ( long long int  d){
	memset (vis, 0, sizeof vis);  
	memset (vis3, 0, sizeof vis3); 
	c=0;
	for ( long long int  i=0; i<200010; i++) g [i].clear();
	for ( long long int  i=0; i<=d; i++){
		if (!vis [i]) dfs (i, d);
	}
	for ( long long int  i=1; i<=d; i++) is_cycle (i);
	if (c) return 0;
	sort_top (d);
	return 1;
}
int  main(){
	 long long int  t; cin >> t;
	while (t--){
		ans.clear ();
		cin >> n >> m;
		long long int  lo=0, hi=2*max(n, m);
		while (lo!=hi){
			 long long int  mid=(lo+hi+1)/2;
			if (ok (mid)) lo=mid;
			else hi=mid-1;
		}
		cout << lo << endl; //cout << ans.size();
		if (lo==0) continue;
		 long long int  pr=0;
		for ( long long int  i=0; i<=lo; i++){
			if (ans [lo]==0) break;
			pr--;
		}
		for ( long long int  i=0; i<=lo; i++){
			//cout << ans [i] << " ";
			o [ans [i]]=pr; pr++;
		}
		for ( long long int  i=1; i<lo+1; i++){
			//cout << o [i] << "x";
			cout << o [i]-o [i-1] << " ";
		}
		cout << endl;
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14292 KB Ok
2 Correct 58 ms 14408 KB Ok
3 Correct 57 ms 14412 KB Ok
4 Correct 62 ms 14292 KB Ok
5 Correct 57 ms 14292 KB Ok
6 Correct 54 ms 14316 KB Ok
7 Correct 55 ms 14384 KB Ok
8 Correct 55 ms 14292 KB Ok
9 Correct 57 ms 14320 KB Ok
10 Correct 55 ms 14308 KB Ok
11 Correct 74 ms 14344 KB Ok
12 Correct 54 ms 14304 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 14292 KB Ok
2 Correct 39 ms 14392 KB Ok
3 Correct 44 ms 14292 KB Ok
4 Correct 44 ms 14400 KB Ok
5 Correct 44 ms 14292 KB Ok
6 Correct 89 ms 14644 KB Ok
7 Correct 135 ms 15768 KB Ok
8 Correct 89 ms 14988 KB Ok
9 Correct 127 ms 16068 KB Ok
10 Correct 111 ms 15236 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14376 KB Ok
2 Correct 29 ms 14292 KB Ok
3 Correct 28 ms 14292 KB Ok
4 Correct 36 ms 14292 KB Ok
5 Correct 28 ms 14292 KB Ok
6 Correct 32 ms 14292 KB Ok
7 Correct 31 ms 14292 KB Ok
8 Correct 32 ms 14392 KB Ok
9 Correct 31 ms 14292 KB Ok
10 Correct 37 ms 14292 KB Ok
11 Correct 41 ms 14292 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14292 KB Ok
2 Correct 37 ms 14292 KB Ok
3 Correct 42 ms 14292 KB Ok
4 Correct 41 ms 14408 KB Ok
5 Correct 45 ms 14420 KB Ok
6 Correct 687 ms 35088 KB Ok
7 Correct 481 ms 35024 KB Ok
8 Correct 1037 ms 38364 KB Ok
9 Correct 790 ms 35820 KB Ok
10 Correct 558 ms 28580 KB Ok
11 Correct 912 ms 40840 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14292 KB Ok
2 Correct 58 ms 14408 KB Ok
3 Correct 57 ms 14412 KB Ok
4 Correct 62 ms 14292 KB Ok
5 Correct 57 ms 14292 KB Ok
6 Correct 54 ms 14316 KB Ok
7 Correct 55 ms 14384 KB Ok
8 Correct 55 ms 14292 KB Ok
9 Correct 57 ms 14320 KB Ok
10 Correct 55 ms 14308 KB Ok
11 Correct 74 ms 14344 KB Ok
12 Correct 54 ms 14304 KB Ok
13 Correct 12 ms 14376 KB Ok
14 Correct 29 ms 14292 KB Ok
15 Correct 28 ms 14292 KB Ok
16 Correct 36 ms 14292 KB Ok
17 Correct 28 ms 14292 KB Ok
18 Correct 32 ms 14292 KB Ok
19 Correct 31 ms 14292 KB Ok
20 Correct 32 ms 14392 KB Ok
21 Correct 31 ms 14292 KB Ok
22 Correct 37 ms 14292 KB Ok
23 Correct 41 ms 14292 KB Ok
24 Correct 89 ms 14548 KB Ok
25 Correct 85 ms 14576 KB Ok
26 Correct 86 ms 14572 KB Ok
27 Correct 82 ms 14552 KB Ok
28 Correct 81 ms 14648 KB Ok
29 Correct 85 ms 14516 KB Ok
30 Correct 88 ms 14544 KB Ok
31 Correct 101 ms 14584 KB Ok
32 Correct 81 ms 14548 KB Ok
33 Correct 98 ms 14600 KB Ok
34 Correct 107 ms 14880 KB Ok
35 Correct 115 ms 14820 KB Ok
36 Correct 93 ms 14876 KB Ok
37 Correct 88 ms 14820 KB Ok
38 Correct 93 ms 14820 KB Ok
39 Correct 91 ms 14828 KB Ok
40 Correct 102 ms 14900 KB Ok
41 Correct 95 ms 14796 KB Ok
42 Correct 105 ms 14988 KB Ok
43 Correct 101 ms 14892 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14292 KB Ok
2 Correct 58 ms 14408 KB Ok
3 Correct 57 ms 14412 KB Ok
4 Correct 62 ms 14292 KB Ok
5 Correct 57 ms 14292 KB Ok
6 Correct 54 ms 14316 KB Ok
7 Correct 55 ms 14384 KB Ok
8 Correct 55 ms 14292 KB Ok
9 Correct 57 ms 14320 KB Ok
10 Correct 55 ms 14308 KB Ok
11 Correct 74 ms 14344 KB Ok
12 Correct 54 ms 14304 KB Ok
13 Correct 27 ms 14292 KB Ok
14 Correct 39 ms 14392 KB Ok
15 Correct 44 ms 14292 KB Ok
16 Correct 44 ms 14400 KB Ok
17 Correct 44 ms 14292 KB Ok
18 Correct 89 ms 14644 KB Ok
19 Correct 135 ms 15768 KB Ok
20 Correct 89 ms 14988 KB Ok
21 Correct 127 ms 16068 KB Ok
22 Correct 111 ms 15236 KB Ok
23 Correct 12 ms 14376 KB Ok
24 Correct 29 ms 14292 KB Ok
25 Correct 28 ms 14292 KB Ok
26 Correct 36 ms 14292 KB Ok
27 Correct 28 ms 14292 KB Ok
28 Correct 32 ms 14292 KB Ok
29 Correct 31 ms 14292 KB Ok
30 Correct 32 ms 14392 KB Ok
31 Correct 31 ms 14292 KB Ok
32 Correct 37 ms 14292 KB Ok
33 Correct 41 ms 14292 KB Ok
34 Correct 89 ms 14548 KB Ok
35 Correct 85 ms 14576 KB Ok
36 Correct 86 ms 14572 KB Ok
37 Correct 82 ms 14552 KB Ok
38 Correct 81 ms 14648 KB Ok
39 Correct 85 ms 14516 KB Ok
40 Correct 88 ms 14544 KB Ok
41 Correct 101 ms 14584 KB Ok
42 Correct 81 ms 14548 KB Ok
43 Correct 98 ms 14600 KB Ok
44 Correct 107 ms 14880 KB Ok
45 Correct 115 ms 14820 KB Ok
46 Correct 93 ms 14876 KB Ok
47 Correct 88 ms 14820 KB Ok
48 Correct 93 ms 14820 KB Ok
49 Correct 91 ms 14828 KB Ok
50 Correct 102 ms 14900 KB Ok
51 Correct 95 ms 14796 KB Ok
52 Correct 105 ms 14988 KB Ok
53 Correct 101 ms 14892 KB Ok
54 Correct 391 ms 20852 KB Ok
55 Correct 440 ms 21312 KB Ok
56 Correct 408 ms 21240 KB Ok
57 Correct 328 ms 20172 KB Ok
58 Correct 421 ms 21100 KB Ok
59 Correct 407 ms 20672 KB Ok
60 Correct 385 ms 20468 KB Ok
61 Correct 320 ms 20524 KB Ok
62 Correct 487 ms 21576 KB Ok
63 Correct 405 ms 20612 KB Ok
64 Correct 450 ms 21216 KB Ok
65 Correct 431 ms 21092 KB Ok
66 Correct 376 ms 20836 KB Ok
67 Correct 332 ms 20372 KB Ok
68 Correct 413 ms 21188 KB Ok
69 Correct 1463 ms 31144 KB Ok
70 Correct 1302 ms 31060 KB Ok
71 Correct 1459 ms 30012 KB Ok
72 Correct 1268 ms 31280 KB Ok
73 Correct 1432 ms 30148 KB Ok
74 Correct 1479 ms 29936 KB Ok
75 Correct 1435 ms 30756 KB Ok
76 Correct 1271 ms 31108 KB Ok
77 Correct 1438 ms 29864 KB Ok
78 Correct 1234 ms 31192 KB Ok
79 Correct 1223 ms 30240 KB Ok
80 Correct 1553 ms 29824 KB Ok
81 Correct 1420 ms 31004 KB Ok
82 Correct 1339 ms 29976 KB Ok
83 Correct 1482 ms 31244 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14292 KB Ok
2 Correct 58 ms 14408 KB Ok
3 Correct 57 ms 14412 KB Ok
4 Correct 62 ms 14292 KB Ok
5 Correct 57 ms 14292 KB Ok
6 Correct 54 ms 14316 KB Ok
7 Correct 55 ms 14384 KB Ok
8 Correct 55 ms 14292 KB Ok
9 Correct 57 ms 14320 KB Ok
10 Correct 55 ms 14308 KB Ok
11 Correct 74 ms 14344 KB Ok
12 Correct 54 ms 14304 KB Ok
13 Correct 27 ms 14292 KB Ok
14 Correct 39 ms 14392 KB Ok
15 Correct 44 ms 14292 KB Ok
16 Correct 44 ms 14400 KB Ok
17 Correct 44 ms 14292 KB Ok
18 Correct 89 ms 14644 KB Ok
19 Correct 135 ms 15768 KB Ok
20 Correct 89 ms 14988 KB Ok
21 Correct 127 ms 16068 KB Ok
22 Correct 111 ms 15236 KB Ok
23 Correct 12 ms 14376 KB Ok
24 Correct 29 ms 14292 KB Ok
25 Correct 28 ms 14292 KB Ok
26 Correct 36 ms 14292 KB Ok
27 Correct 28 ms 14292 KB Ok
28 Correct 32 ms 14292 KB Ok
29 Correct 31 ms 14292 KB Ok
30 Correct 32 ms 14392 KB Ok
31 Correct 31 ms 14292 KB Ok
32 Correct 37 ms 14292 KB Ok
33 Correct 41 ms 14292 KB Ok
34 Correct 31 ms 14292 KB Ok
35 Correct 37 ms 14292 KB Ok
36 Correct 42 ms 14292 KB Ok
37 Correct 41 ms 14408 KB Ok
38 Correct 45 ms 14420 KB Ok
39 Correct 687 ms 35088 KB Ok
40 Correct 481 ms 35024 KB Ok
41 Correct 1037 ms 38364 KB Ok
42 Correct 790 ms 35820 KB Ok
43 Correct 558 ms 28580 KB Ok
44 Correct 912 ms 40840 KB Ok
45 Correct 89 ms 14548 KB Ok
46 Correct 85 ms 14576 KB Ok
47 Correct 86 ms 14572 KB Ok
48 Correct 82 ms 14552 KB Ok
49 Correct 81 ms 14648 KB Ok
50 Correct 85 ms 14516 KB Ok
51 Correct 88 ms 14544 KB Ok
52 Correct 101 ms 14584 KB Ok
53 Correct 81 ms 14548 KB Ok
54 Correct 98 ms 14600 KB Ok
55 Correct 107 ms 14880 KB Ok
56 Correct 115 ms 14820 KB Ok
57 Correct 93 ms 14876 KB Ok
58 Correct 88 ms 14820 KB Ok
59 Correct 93 ms 14820 KB Ok
60 Correct 91 ms 14828 KB Ok
61 Correct 102 ms 14900 KB Ok
62 Correct 95 ms 14796 KB Ok
63 Correct 105 ms 14988 KB Ok
64 Correct 101 ms 14892 KB Ok
65 Correct 391 ms 20852 KB Ok
66 Correct 440 ms 21312 KB Ok
67 Correct 408 ms 21240 KB Ok
68 Correct 328 ms 20172 KB Ok
69 Correct 421 ms 21100 KB Ok
70 Correct 407 ms 20672 KB Ok
71 Correct 385 ms 20468 KB Ok
72 Correct 320 ms 20524 KB Ok
73 Correct 487 ms 21576 KB Ok
74 Correct 405 ms 20612 KB Ok
75 Correct 450 ms 21216 KB Ok
76 Correct 431 ms 21092 KB Ok
77 Correct 376 ms 20836 KB Ok
78 Correct 332 ms 20372 KB Ok
79 Correct 413 ms 21188 KB Ok
80 Correct 1463 ms 31144 KB Ok
81 Correct 1302 ms 31060 KB Ok
82 Correct 1459 ms 30012 KB Ok
83 Correct 1268 ms 31280 KB Ok
84 Correct 1432 ms 30148 KB Ok
85 Correct 1479 ms 29936 KB Ok
86 Correct 1435 ms 30756 KB Ok
87 Correct 1271 ms 31108 KB Ok
88 Correct 1438 ms 29864 KB Ok
89 Correct 1234 ms 31192 KB Ok
90 Correct 1223 ms 30240 KB Ok
91 Correct 1553 ms 29824 KB Ok
92 Correct 1420 ms 31004 KB Ok
93 Correct 1339 ms 29976 KB Ok
94 Correct 1482 ms 31244 KB Ok
95 Incorrect 1075 ms 39080 KB Jury has the better answer : jans = 216945, pans = 215705
96 Halted 0 ms 0 KB -