oj.uz

Submission #386848

# Submission time Handle Problem Language Result Execution time Memory
386848 2021-04-07T13:36:44 Z vanic Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 84160 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
 
using namespace std;
 
const int maxn=1e6+5;
 
int n, m;
bool bio[maxn];
bool put[maxn];
int sz;
 
bool siri(int x){
	bio[x]=1;
	put[x]=1;
//	cout << x << endl;
	if(x+m<sz){
		if(put[x+m]){
			return 1;
		}
		if(!bio[x+m]){
			if(siri(x+m)){
				return 1;
			}
		}
	}
	if(x-n>-1){
		if(put[x-n]){
			return 1;
		}
		if(!bio[x-n]){
			if(siri(x-n)){
				return 1;
			}
		}
	}
	put[x]=0;
	return 0;
}
 
bool provjeri(int x){
	sz=x+1;
	for(int i=0; i<sz; i++){
		bio[i]=0;
		put[i]=0;
	}
	for(int i=0; i<sz; i++){
		if(!bio[i]){
			if(siri(i)){
				return 0;
			}
		}
	}
	return 1;
}

int binary(){
	int lo=0, hi=4e5, mid;
	while(lo<hi){
		mid=(lo+hi)/2+1;
		if(provjeri(mid)){
			lo=mid;
		}
		else{
			hi=mid-1;
		}
	}
	return lo;
}

vector < int > ms[maxn];
vector < int > top;

void dodaj(int x){
	bio[x]=1;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(!bio[ms[x][i]]){
			dodaj(ms[x][i]);
		}
	}
	top.push_back(x);
}

int val[maxn];

void rijesi(int x){
	sz=x+1;
	for(int i=0; i<sz; i++){
		bio[i]=0;
		if(i>=n){
			ms[i-n].push_back(i);
		}
		if(i>=m){
			ms[i].push_back(i-m);
		}
	}
	for(int i=0; i<sz; i++){
		if(!bio[i]){
			dodaj(i);
		}
	}
	for(int i=0; i<sz; i++){
//		cout << top[i] << ' ';
		val[top[i]]=i;
	}
//	cout << endl;
	top.clear();
	ms[0].clear();
	for(int i=1; i<sz; i++){
		ms[i].clear();
		cout << val[i]-val[i-1] << ' ';
	}
	cout << '\n';
}

void solve(){
	cin >> n >> m;
	int sol=binary();
	cout << sol << '\n';
	rijesi(sol);
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 33644 KB Ok
2 Correct 52 ms 33644 KB Ok
3 Correct 23 ms 24812 KB Ok
4 Correct 24 ms 25580 KB Ok
5 Correct 23 ms 24812 KB Ok
6 Correct 25 ms 26604 KB Ok
7 Correct 24 ms 24684 KB Ok
8 Correct 24 ms 26220 KB Ok
9 Correct 23 ms 24812 KB Ok
10 Correct 24 ms 25068 KB Ok
11 Correct 23 ms 24684 KB Ok
12 Correct 23 ms 24556 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 28908 KB Ok
2 Correct 36 ms 28908 KB Ok
3 Correct 32 ms 28908 KB Ok
4 Correct 35 ms 28908 KB Ok
5 Correct 33 ms 29036 KB Ok
6 Correct 36 ms 29164 KB Ok
7 Correct 62 ms 29932 KB Ok
8 Correct 40 ms 29420 KB Ok
9 Correct 58 ms 30112 KB Ok
10 Correct 43 ms 29676 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33772 KB Ok
2 Correct 56 ms 33644 KB Ok
3 Correct 40 ms 33644 KB Ok
4 Correct 37 ms 33644 KB Ok
5 Correct 32 ms 27404 KB Ok
6 Correct 33 ms 28908 KB Ok
7 Correct 28 ms 26092 KB Ok
8 Correct 31 ms 28908 KB Ok
9 Correct 36 ms 29036 KB Ok
10 Correct 35 ms 33644 KB Ok
11 Correct 35 ms 33644 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 27372 KB Ok
2 Correct 27 ms 25580 KB Ok
3 Correct 25 ms 25068 KB Ok
4 Correct 25 ms 24812 KB Ok
5 Correct 25 ms 24684 KB Ok
6 Correct 317 ms 41696 KB Ok
7 Correct 300 ms 43360 KB Ok
8 Correct 548 ms 46168 KB Ok
9 Correct 402 ms 43360 KB Ok
10 Correct 235 ms 34916 KB Ok
11 Correct 404 ms 44780 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 33644 KB Ok
2 Correct 52 ms 33644 KB Ok
3 Correct 23 ms 24812 KB Ok
4 Correct 24 ms 25580 KB Ok
5 Correct 23 ms 24812 KB Ok
6 Correct 25 ms 26604 KB Ok
7 Correct 24 ms 24684 KB Ok
8 Correct 24 ms 26220 KB Ok
9 Correct 23 ms 24812 KB Ok
10 Correct 24 ms 25068 KB Ok
11 Correct 23 ms 24684 KB Ok
12 Correct 23 ms 24556 KB Ok
13 Correct 30 ms 33772 KB Ok
14 Correct 56 ms 33644 KB Ok
15 Correct 40 ms 33644 KB Ok
16 Correct 37 ms 33644 KB Ok
17 Correct 32 ms 27404 KB Ok
18 Correct 33 ms 28908 KB Ok
19 Correct 28 ms 26092 KB Ok
20 Correct 31 ms 28908 KB Ok
21 Correct 36 ms 29036 KB Ok
22 Correct 35 ms 33644 KB Ok
23 Correct 35 ms 33644 KB Ok
24 Correct 27 ms 24480 KB Ok
25 Correct 27 ms 24428 KB Ok
26 Correct 27 ms 24428 KB Ok
27 Correct 27 ms 24428 KB Ok
28 Correct 26 ms 24556 KB Ok
29 Correct 26 ms 24428 KB Ok
30 Correct 27 ms 24812 KB Ok
31 Correct 27 ms 24428 KB Ok
32 Correct 28 ms 24428 KB Ok
33 Correct 27 ms 24428 KB Ok
34 Correct 33 ms 24684 KB Ok
35 Correct 39 ms 24684 KB Ok
36 Correct 34 ms 24684 KB Ok
37 Correct 35 ms 24684 KB Ok
38 Correct 34 ms 24684 KB Ok
39 Correct 33 ms 24684 KB Ok
40 Correct 37 ms 24684 KB Ok
41 Correct 34 ms 24684 KB Ok
42 Correct 34 ms 24684 KB Ok
43 Correct 37 ms 24684 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 33644 KB Ok
2 Correct 52 ms 33644 KB Ok
3 Correct 23 ms 24812 KB Ok
4 Correct 24 ms 25580 KB Ok
5 Correct 23 ms 24812 KB Ok
6 Correct 25 ms 26604 KB Ok
7 Correct 24 ms 24684 KB Ok
8 Correct 24 ms 26220 KB Ok
9 Correct 23 ms 24812 KB Ok
10 Correct 24 ms 25068 KB Ok
11 Correct 23 ms 24684 KB Ok
12 Correct 23 ms 24556 KB Ok
13 Correct 41 ms 28908 KB Ok
14 Correct 36 ms 28908 KB Ok
15 Correct 32 ms 28908 KB Ok
16 Correct 35 ms 28908 KB Ok
17 Correct 33 ms 29036 KB Ok
18 Correct 36 ms 29164 KB Ok
19 Correct 62 ms 29932 KB Ok
20 Correct 40 ms 29420 KB Ok
21 Correct 58 ms 30112 KB Ok
22 Correct 43 ms 29676 KB Ok
23 Correct 30 ms 33772 KB Ok
24 Correct 56 ms 33644 KB Ok
25 Correct 40 ms 33644 KB Ok
26 Correct 37 ms 33644 KB Ok
27 Correct 32 ms 27404 KB Ok
28 Correct 33 ms 28908 KB Ok
29 Correct 28 ms 26092 KB Ok
30 Correct 31 ms 28908 KB Ok
31 Correct 36 ms 29036 KB Ok
32 Correct 35 ms 33644 KB Ok
33 Correct 35 ms 33644 KB Ok
34 Correct 27 ms 24480 KB Ok
35 Correct 27 ms 24428 KB Ok
36 Correct 27 ms 24428 KB Ok
37 Correct 27 ms 24428 KB Ok
38 Correct 26 ms 24556 KB Ok
39 Correct 26 ms 24428 KB Ok
40 Correct 27 ms 24812 KB Ok
41 Correct 27 ms 24428 KB Ok
42 Correct 28 ms 24428 KB Ok
43 Correct 27 ms 24428 KB Ok
44 Correct 33 ms 24684 KB Ok
45 Correct 39 ms 24684 KB Ok
46 Correct 34 ms 24684 KB Ok
47 Correct 35 ms 24684 KB Ok
48 Correct 34 ms 24684 KB Ok
49 Correct 33 ms 24684 KB Ok
50 Correct 37 ms 24684 KB Ok
51 Correct 34 ms 24684 KB Ok
52 Correct 34 ms 24684 KB Ok
53 Correct 37 ms 24684 KB Ok
54 Correct 158 ms 29616 KB Ok
55 Correct 199 ms 29800 KB Ok
56 Correct 196 ms 29932 KB Ok
57 Correct 135 ms 29036 KB Ok
58 Correct 166 ms 29292 KB Ok
59 Correct 159 ms 28900 KB Ok
60 Correct 139 ms 28644 KB Ok
61 Correct 141 ms 29292 KB Ok
62 Correct 187 ms 29796 KB Ok
63 Correct 148 ms 29036 KB Ok
64 Correct 184 ms 29804 KB Ok
65 Correct 182 ms 29420 KB Ok
66 Correct 153 ms 29292 KB Ok
67 Correct 135 ms 29036 KB Ok
68 Correct 160 ms 29412 KB Ok
69 Correct 455 ms 39036 KB Ok
70 Correct 487 ms 39524 KB Ok
71 Correct 431 ms 39012 KB Ok
72 Correct 494 ms 39012 KB Ok
73 Correct 425 ms 39012 KB Ok
74 Correct 433 ms 39012 KB Ok
75 Correct 406 ms 38500 KB Ok
76 Correct 476 ms 39200 KB Ok
77 Correct 407 ms 38548 KB Ok
78 Correct 495 ms 39140 KB Ok
79 Correct 455 ms 39396 KB Ok
80 Correct 443 ms 39268 KB Ok
81 Correct 459 ms 39268 KB Ok
82 Correct 471 ms 39140 KB Ok
83 Correct 420 ms 38628 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 33644 KB Ok
2 Correct 52 ms 33644 KB Ok
3 Correct 23 ms 24812 KB Ok
4 Correct 24 ms 25580 KB Ok
5 Correct 23 ms 24812 KB Ok
6 Correct 25 ms 26604 KB Ok
7 Correct 24 ms 24684 KB Ok
8 Correct 24 ms 26220 KB Ok
9 Correct 23 ms 24812 KB Ok
10 Correct 24 ms 25068 KB Ok
11 Correct 23 ms 24684 KB Ok
12 Correct 23 ms 24556 KB Ok
13 Correct 41 ms 28908 KB Ok
14 Correct 36 ms 28908 KB Ok
15 Correct 32 ms 28908 KB Ok
16 Correct 35 ms 28908 KB Ok
17 Correct 33 ms 29036 KB Ok
18 Correct 36 ms 29164 KB Ok
19 Correct 62 ms 29932 KB Ok
20 Correct 40 ms 29420 KB Ok
21 Correct 58 ms 30112 KB Ok
22 Correct 43 ms 29676 KB Ok
23 Correct 30 ms 33772 KB Ok
24 Correct 56 ms 33644 KB Ok
25 Correct 40 ms 33644 KB Ok
26 Correct 37 ms 33644 KB Ok
27 Correct 32 ms 27404 KB Ok
28 Correct 33 ms 28908 KB Ok
29 Correct 28 ms 26092 KB Ok
30 Correct 31 ms 28908 KB Ok
31 Correct 36 ms 29036 KB Ok
32 Correct 35 ms 33644 KB Ok
33 Correct 35 ms 33644 KB Ok
34 Correct 30 ms 27372 KB Ok
35 Correct 27 ms 25580 KB Ok
36 Correct 25 ms 25068 KB Ok
37 Correct 25 ms 24812 KB Ok
38 Correct 25 ms 24684 KB Ok
39 Correct 317 ms 41696 KB Ok
40 Correct 300 ms 43360 KB Ok
41 Correct 548 ms 46168 KB Ok
42 Correct 402 ms 43360 KB Ok
43 Correct 235 ms 34916 KB Ok
44 Correct 404 ms 44780 KB Ok
45 Correct 27 ms 24480 KB Ok
46 Correct 27 ms 24428 KB Ok
47 Correct 27 ms 24428 KB Ok
48 Correct 27 ms 24428 KB Ok
49 Correct 26 ms 24556 KB Ok
50 Correct 26 ms 24428 KB Ok
51 Correct 27 ms 24812 KB Ok
52 Correct 27 ms 24428 KB Ok
53 Correct 28 ms 24428 KB Ok
54 Correct 27 ms 24428 KB Ok
55 Correct 33 ms 24684 KB Ok
56 Correct 39 ms 24684 KB Ok
57 Correct 34 ms 24684 KB Ok
58 Correct 35 ms 24684 KB Ok
59 Correct 34 ms 24684 KB Ok
60 Correct 33 ms 24684 KB Ok
61 Correct 37 ms 24684 KB Ok
62 Correct 34 ms 24684 KB Ok
63 Correct 34 ms 24684 KB Ok
64 Correct 37 ms 24684 KB Ok
65 Correct 158 ms 29616 KB Ok
66 Correct 199 ms 29800 KB Ok
67 Correct 196 ms 29932 KB Ok
68 Correct 135 ms 29036 KB Ok
69 Correct 166 ms 29292 KB Ok
70 Correct 159 ms 28900 KB Ok
71 Correct 139 ms 28644 KB Ok
72 Correct 141 ms 29292 KB Ok
73 Correct 187 ms 29796 KB Ok
74 Correct 148 ms 29036 KB Ok
75 Correct 184 ms 29804 KB Ok
76 Correct 182 ms 29420 KB Ok
77 Correct 153 ms 29292 KB Ok
78 Correct 135 ms 29036 KB Ok
79 Correct 160 ms 29412 KB Ok
80 Correct 455 ms 39036 KB Ok
81 Correct 487 ms 39524 KB Ok
82 Correct 431 ms 39012 KB Ok
83 Correct 494 ms 39012 KB Ok
84 Correct 425 ms 39012 KB Ok
85 Correct 433 ms 39012 KB Ok
86 Correct 406 ms 38500 KB Ok
87 Correct 476 ms 39200 KB Ok
88 Correct 407 ms 38548 KB Ok
89 Correct 495 ms 39140 KB Ok
90 Correct 455 ms 39396 KB Ok
91 Correct 443 ms 39268 KB Ok
92 Correct 459 ms 39268 KB Ok
93 Correct 471 ms 39140 KB Ok
94 Correct 420 ms 38628 KB Ok
95 Correct 387 ms 38248 KB Ok
96 Correct 606 ms 44128 KB Ok
97 Correct 523 ms 40668 KB Ok
98 Correct 386 ms 40804 KB Ok
99 Correct 472 ms 40152 KB Ok
100 Correct 478 ms 39776 KB Ok
101 Correct 507 ms 42468 KB Ok
102 Correct 484 ms 40880 KB Ok
103 Correct 496 ms 41728 KB Ok
104 Correct 561 ms 43488 KB Ok
105 Correct 526 ms 44124 KB Ok
106 Correct 528 ms 44256 KB Ok
107 Correct 531 ms 43060 KB Ok
108 Correct 581 ms 43740 KB Ok
109 Correct 509 ms 45020 KB Ok
110 Execution timed out 2049 ms 84160 KB Time limit exceeded
111 Halted 0 ms 0 KB -