oj.uz

Submission #634988

# Submission time Handle Problem Language Result Execution time Memory
634988 2022-08-25T09:59:05 Z drkarlicio2107 Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 47424 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<400010; 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 48 ms 14292 KB Ok
2 Correct 99 ms 14292 KB Ok
3 Correct 90 ms 14408 KB Ok
4 Correct 92 ms 14292 KB Ok
5 Correct 99 ms 14292 KB Ok
6 Correct 89 ms 14364 KB Ok
7 Correct 90 ms 14368 KB Ok
8 Correct 100 ms 14332 KB Ok
9 Correct 95 ms 14292 KB Ok
10 Correct 92 ms 14292 KB Ok
11 Correct 95 ms 14292 KB Ok
12 Correct 97 ms 14368 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14284 KB Ok
2 Correct 61 ms 14292 KB Ok
3 Correct 68 ms 14368 KB Ok
4 Correct 78 ms 14292 KB Ok
5 Correct 87 ms 14308 KB Ok
6 Correct 151 ms 14668 KB Ok
7 Correct 194 ms 15796 KB Ok
8 Correct 152 ms 15132 KB Ok
9 Correct 206 ms 16052 KB Ok
10 Correct 168 ms 15288 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14292 KB Ok
2 Correct 48 ms 14368 KB Ok
3 Correct 44 ms 14336 KB Ok
4 Correct 48 ms 14368 KB Ok
5 Correct 45 ms 14292 KB Ok
6 Correct 52 ms 14368 KB Ok
7 Correct 53 ms 14404 KB Ok
8 Correct 48 ms 14292 KB Ok
9 Correct 53 ms 14400 KB Ok
10 Correct 66 ms 14292 KB Ok
11 Correct 60 ms 14396 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14292 KB Ok
2 Correct 56 ms 14396 KB Ok
3 Correct 62 ms 14360 KB Ok
4 Correct 70 ms 14368 KB Ok
5 Correct 74 ms 14292 KB Ok
6 Correct 796 ms 35160 KB Ok
7 Correct 566 ms 35088 KB Ok
8 Correct 1099 ms 38376 KB Ok
9 Correct 873 ms 35980 KB Ok
10 Correct 569 ms 28456 KB Ok
11 Correct 983 ms 40704 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14292 KB Ok
2 Correct 99 ms 14292 KB Ok
3 Correct 90 ms 14408 KB Ok
4 Correct 92 ms 14292 KB Ok
5 Correct 99 ms 14292 KB Ok
6 Correct 89 ms 14364 KB Ok
7 Correct 90 ms 14368 KB Ok
8 Correct 100 ms 14332 KB Ok
9 Correct 95 ms 14292 KB Ok
10 Correct 92 ms 14292 KB Ok
11 Correct 95 ms 14292 KB Ok
12 Correct 97 ms 14368 KB Ok
13 Correct 15 ms 14292 KB Ok
14 Correct 48 ms 14368 KB Ok
15 Correct 44 ms 14336 KB Ok
16 Correct 48 ms 14368 KB Ok
17 Correct 45 ms 14292 KB Ok
18 Correct 52 ms 14368 KB Ok
19 Correct 53 ms 14404 KB Ok
20 Correct 48 ms 14292 KB Ok
21 Correct 53 ms 14400 KB Ok
22 Correct 66 ms 14292 KB Ok
23 Correct 60 ms 14396 KB Ok
24 Correct 144 ms 14564 KB Ok
25 Correct 145 ms 14576 KB Ok
26 Correct 142 ms 14584 KB Ok
27 Correct 146 ms 14576 KB Ok
28 Correct 140 ms 14668 KB Ok
29 Correct 152 ms 14540 KB Ok
30 Correct 136 ms 14500 KB Ok
31 Correct 138 ms 14552 KB Ok
32 Correct 141 ms 14564 KB Ok
33 Correct 144 ms 14484 KB Ok
34 Correct 168 ms 14884 KB Ok
35 Correct 152 ms 14796 KB Ok
36 Correct 148 ms 14912 KB Ok
37 Correct 145 ms 14864 KB Ok
38 Correct 158 ms 14792 KB Ok
39 Correct 146 ms 14784 KB Ok
40 Correct 154 ms 14904 KB Ok
41 Correct 156 ms 14900 KB Ok
42 Correct 166 ms 14856 KB Ok
43 Correct 147 ms 14936 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14292 KB Ok
2 Correct 99 ms 14292 KB Ok
3 Correct 90 ms 14408 KB Ok
4 Correct 92 ms 14292 KB Ok
5 Correct 99 ms 14292 KB Ok
6 Correct 89 ms 14364 KB Ok
7 Correct 90 ms 14368 KB Ok
8 Correct 100 ms 14332 KB Ok
9 Correct 95 ms 14292 KB Ok
10 Correct 92 ms 14292 KB Ok
11 Correct 95 ms 14292 KB Ok
12 Correct 97 ms 14368 KB Ok
13 Correct 45 ms 14284 KB Ok
14 Correct 61 ms 14292 KB Ok
15 Correct 68 ms 14368 KB Ok
16 Correct 78 ms 14292 KB Ok
17 Correct 87 ms 14308 KB Ok
18 Correct 151 ms 14668 KB Ok
19 Correct 194 ms 15796 KB Ok
20 Correct 152 ms 15132 KB Ok
21 Correct 206 ms 16052 KB Ok
22 Correct 168 ms 15288 KB Ok
23 Correct 15 ms 14292 KB Ok
24 Correct 48 ms 14368 KB Ok
25 Correct 44 ms 14336 KB Ok
26 Correct 48 ms 14368 KB Ok
27 Correct 45 ms 14292 KB Ok
28 Correct 52 ms 14368 KB Ok
29 Correct 53 ms 14404 KB Ok
30 Correct 48 ms 14292 KB Ok
31 Correct 53 ms 14400 KB Ok
32 Correct 66 ms 14292 KB Ok
33 Correct 60 ms 14396 KB Ok
34 Correct 144 ms 14564 KB Ok
35 Correct 145 ms 14576 KB Ok
36 Correct 142 ms 14584 KB Ok
37 Correct 146 ms 14576 KB Ok
38 Correct 140 ms 14668 KB Ok
39 Correct 152 ms 14540 KB Ok
40 Correct 136 ms 14500 KB Ok
41 Correct 138 ms 14552 KB Ok
42 Correct 141 ms 14564 KB Ok
43 Correct 144 ms 14484 KB Ok
44 Correct 168 ms 14884 KB Ok
45 Correct 152 ms 14796 KB Ok
46 Correct 148 ms 14912 KB Ok
47 Correct 145 ms 14864 KB Ok
48 Correct 158 ms 14792 KB Ok
49 Correct 146 ms 14784 KB Ok
50 Correct 154 ms 14904 KB Ok
51 Correct 156 ms 14900 KB Ok
52 Correct 166 ms 14856 KB Ok
53 Correct 147 ms 14936 KB Ok
54 Correct 455 ms 20888 KB Ok
55 Correct 512 ms 21304 KB Ok
56 Correct 499 ms 21296 KB Ok
57 Correct 407 ms 20200 KB Ok
58 Correct 492 ms 21232 KB Ok
59 Correct 514 ms 20732 KB Ok
60 Correct 425 ms 20332 KB Ok
61 Correct 444 ms 20624 KB Ok
62 Correct 569 ms 21556 KB Ok
63 Correct 480 ms 20668 KB Ok
64 Correct 541 ms 21296 KB Ok
65 Correct 493 ms 21076 KB Ok
66 Correct 432 ms 20764 KB Ok
67 Correct 425 ms 20360 KB Ok
68 Correct 523 ms 21020 KB Ok
69 Correct 1584 ms 31260 KB Ok
70 Correct 1292 ms 31016 KB Ok
71 Correct 1472 ms 29888 KB Ok
72 Correct 1559 ms 31316 KB Ok
73 Correct 1395 ms 30144 KB Ok
74 Correct 1509 ms 29884 KB Ok
75 Correct 1341 ms 30844 KB Ok
76 Correct 1259 ms 31108 KB Ok
77 Correct 1405 ms 29776 KB Ok
78 Correct 1415 ms 31340 KB Ok
79 Correct 1396 ms 30336 KB Ok
80 Correct 1381 ms 29880 KB Ok
81 Correct 1298 ms 31036 KB Ok
82 Correct 1540 ms 30072 KB Ok
83 Correct 1516 ms 31188 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14292 KB Ok
2 Correct 99 ms 14292 KB Ok
3 Correct 90 ms 14408 KB Ok
4 Correct 92 ms 14292 KB Ok
5 Correct 99 ms 14292 KB Ok
6 Correct 89 ms 14364 KB Ok
7 Correct 90 ms 14368 KB Ok
8 Correct 100 ms 14332 KB Ok
9 Correct 95 ms 14292 KB Ok
10 Correct 92 ms 14292 KB Ok
11 Correct 95 ms 14292 KB Ok
12 Correct 97 ms 14368 KB Ok
13 Correct 45 ms 14284 KB Ok
14 Correct 61 ms 14292 KB Ok
15 Correct 68 ms 14368 KB Ok
16 Correct 78 ms 14292 KB Ok
17 Correct 87 ms 14308 KB Ok
18 Correct 151 ms 14668 KB Ok
19 Correct 194 ms 15796 KB Ok
20 Correct 152 ms 15132 KB Ok
21 Correct 206 ms 16052 KB Ok
22 Correct 168 ms 15288 KB Ok
23 Correct 15 ms 14292 KB Ok
24 Correct 48 ms 14368 KB Ok
25 Correct 44 ms 14336 KB Ok
26 Correct 48 ms 14368 KB Ok
27 Correct 45 ms 14292 KB Ok
28 Correct 52 ms 14368 KB Ok
29 Correct 53 ms 14404 KB Ok
30 Correct 48 ms 14292 KB Ok
31 Correct 53 ms 14400 KB Ok
32 Correct 66 ms 14292 KB Ok
33 Correct 60 ms 14396 KB Ok
34 Correct 47 ms 14292 KB Ok
35 Correct 56 ms 14396 KB Ok
36 Correct 62 ms 14360 KB Ok
37 Correct 70 ms 14368 KB Ok
38 Correct 74 ms 14292 KB Ok
39 Correct 796 ms 35160 KB Ok
40 Correct 566 ms 35088 KB Ok
41 Correct 1099 ms 38376 KB Ok
42 Correct 873 ms 35980 KB Ok
43 Correct 569 ms 28456 KB Ok
44 Correct 983 ms 40704 KB Ok
45 Correct 144 ms 14564 KB Ok
46 Correct 145 ms 14576 KB Ok
47 Correct 142 ms 14584 KB Ok
48 Correct 146 ms 14576 KB Ok
49 Correct 140 ms 14668 KB Ok
50 Correct 152 ms 14540 KB Ok
51 Correct 136 ms 14500 KB Ok
52 Correct 138 ms 14552 KB Ok
53 Correct 141 ms 14564 KB Ok
54 Correct 144 ms 14484 KB Ok
55 Correct 168 ms 14884 KB Ok
56 Correct 152 ms 14796 KB Ok
57 Correct 148 ms 14912 KB Ok
58 Correct 145 ms 14864 KB Ok
59 Correct 158 ms 14792 KB Ok
60 Correct 146 ms 14784 KB Ok
61 Correct 154 ms 14904 KB Ok
62 Correct 156 ms 14900 KB Ok
63 Correct 166 ms 14856 KB Ok
64 Correct 147 ms 14936 KB Ok
65 Correct 455 ms 20888 KB Ok
66 Correct 512 ms 21304 KB Ok
67 Correct 499 ms 21296 KB Ok
68 Correct 407 ms 20200 KB Ok
69 Correct 492 ms 21232 KB Ok
70 Correct 514 ms 20732 KB Ok
71 Correct 425 ms 20332 KB Ok
72 Correct 444 ms 20624 KB Ok
73 Correct 569 ms 21556 KB Ok
74 Correct 480 ms 20668 KB Ok
75 Correct 541 ms 21296 KB Ok
76 Correct 493 ms 21076 KB Ok
77 Correct 432 ms 20764 KB Ok
78 Correct 425 ms 20360 KB Ok
79 Correct 523 ms 21020 KB Ok
80 Correct 1584 ms 31260 KB Ok
81 Correct 1292 ms 31016 KB Ok
82 Correct 1472 ms 29888 KB Ok
83 Correct 1559 ms 31316 KB Ok
84 Correct 1395 ms 30144 KB Ok
85 Correct 1509 ms 29884 KB Ok
86 Correct 1341 ms 30844 KB Ok
87 Correct 1259 ms 31108 KB Ok
88 Correct 1405 ms 29776 KB Ok
89 Correct 1415 ms 31340 KB Ok
90 Correct 1396 ms 30336 KB Ok
91 Correct 1381 ms 29880 KB Ok
92 Correct 1298 ms 31036 KB Ok
93 Correct 1540 ms 30072 KB Ok
94 Correct 1516 ms 31188 KB Ok
95 Correct 1055 ms 31820 KB Ok
96 Correct 1527 ms 40052 KB Ok
97 Correct 1547 ms 35804 KB Ok
98 Correct 992 ms 35948 KB Ok
99 Correct 1160 ms 34500 KB Ok
100 Correct 1341 ms 35704 KB Ok
101 Correct 1263 ms 37064 KB Ok
102 Correct 1200 ms 35684 KB Ok
103 Correct 1383 ms 37596 KB Ok
104 Correct 1520 ms 38876 KB Ok
105 Correct 1512 ms 39552 KB Ok
106 Correct 1160 ms 38240 KB Ok
107 Correct 1354 ms 37976 KB Ok
108 Correct 1647 ms 39808 KB Ok
109 Correct 1401 ms 39992 KB Ok
110 Execution timed out 2092 ms 47424 KB Time limit exceeded
111 Halted 0 ms 0 KB -