oj.uz

Submission #386856

# Submission time Handle Problem Language Result Execution time Memory
386856 2021-04-07T13:44:23 Z vanic Nice sequence (IZhO18_sequence) C++14
100 / 100
 1661 ms 51500 KB 
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
 
using namespace std;
 
const int maxn=4e5+5;
 
int n, m;
bitset < maxn > bio;
bitset < maxn > put;
int sz;
 
bool siri(int x){
	bio[x]=1;
	put[x]=1;
	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;
	bio.reset();
	put.reset();
	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 > top;

void dodaj(int x){
	bio[x]=1;
	if(x+n<sz && !bio[x+n]){
		dodaj(x+n);
	}
	if(x-m>-1 && !bio[x-m]){
		dodaj(x-m);
	}
	top.push_back(x);
}

int val[maxn];

void rijesi(int x){
	sz=x+1;
	bio.reset();
	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();
	for(int i=1; i<sz; i++){
		printf("%d ", val[i]-val[i-1]);
	}
	printf("\n");
}

void solve(){
	scanf("%d%d", &n, &m);
	int sol=binary();
	printf("%d\n", sol);
	rijesi(sol);
}
 
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		solve();
	}
	return 0;
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9836 KB Ok
2 Correct 30 ms 9836 KB Ok
3 Correct 3 ms 876 KB Ok
4 Correct 3 ms 1772 KB Ok
5 Correct 3 ms 876 KB Ok
6 Correct 4 ms 2796 KB Ok
7 Correct 4 ms 876 KB Ok
8 Correct 4 ms 2284 KB Ok
9 Correct 3 ms 1004 KB Ok
10 Correct 3 ms 1260 KB Ok
11 Correct 2 ms 876 KB Ok
12 Correct 3 ms 748 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5120 KB Ok
2 Correct 17 ms 5100 KB Ok
3 Correct 12 ms 5100 KB Ok
4 Correct 17 ms 5228 KB Ok
5 Correct 14 ms 5100 KB Ok
6 Correct 18 ms 5228 KB Ok
7 Correct 30 ms 5868 KB Ok
8 Correct 19 ms 5484 KB Ok
9 Correct 35 ms 5996 KB Ok
10 Correct 22 ms 5612 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9836 KB Ok
2 Correct 34 ms 9836 KB Ok
3 Correct 22 ms 9836 KB Ok
4 Correct 19 ms 9836 KB Ok
5 Correct 11 ms 3564 KB Ok
6 Correct 11 ms 5100 KB Ok
7 Correct 8 ms 2284 KB Ok
8 Correct 11 ms 5100 KB Ok
9 Correct 12 ms 5100 KB Ok
10 Correct 15 ms 9836 KB Ok
11 Correct 15 ms 9836 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3564 KB Ok
2 Correct 7 ms 1772 KB Ok
3 Correct 5 ms 1132 KB Ok
4 Correct 4 ms 1004 KB Ok
5 Correct 4 ms 876 KB Ok
6 Correct 268 ms 12384 KB Ok
7 Correct 266 ms 13664 KB Ok
8 Correct 469 ms 16352 KB Ok
9 Correct 347 ms 14424 KB Ok
10 Correct 188 ms 7396 KB Ok
11 Correct 348 ms 14944 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9836 KB Ok
2 Correct 30 ms 9836 KB Ok
3 Correct 3 ms 876 KB Ok
4 Correct 3 ms 1772 KB Ok
5 Correct 3 ms 876 KB Ok
6 Correct 4 ms 2796 KB Ok
7 Correct 4 ms 876 KB Ok
8 Correct 4 ms 2284 KB Ok
9 Correct 3 ms 1004 KB Ok
10 Correct 3 ms 1260 KB Ok
11 Correct 2 ms 876 KB Ok
12 Correct 3 ms 748 KB Ok
13 Correct 16 ms 9836 KB Ok
14 Correct 34 ms 9836 KB Ok
15 Correct 22 ms 9836 KB Ok
16 Correct 19 ms 9836 KB Ok
17 Correct 11 ms 3564 KB Ok
18 Correct 11 ms 5100 KB Ok
19 Correct 8 ms 2284 KB Ok
20 Correct 11 ms 5100 KB Ok
21 Correct 12 ms 5100 KB Ok
22 Correct 15 ms 9836 KB Ok
23 Correct 15 ms 9836 KB Ok
24 Correct 4 ms 492 KB Ok
25 Correct 5 ms 492 KB Ok
26 Correct 5 ms 492 KB Ok
27 Correct 4 ms 492 KB Ok
28 Correct 4 ms 620 KB Ok
29 Correct 4 ms 492 KB Ok
30 Correct 4 ms 876 KB Ok
31 Correct 4 ms 492 KB Ok
32 Correct 6 ms 492 KB Ok
33 Correct 5 ms 492 KB Ok
34 Correct 12 ms 748 KB Ok
35 Correct 13 ms 748 KB Ok
36 Correct 11 ms 748 KB Ok
37 Correct 12 ms 748 KB Ok
38 Correct 11 ms 748 KB Ok
39 Correct 10 ms 748 KB Ok
40 Correct 12 ms 748 KB Ok
41 Correct 12 ms 748 KB Ok
42 Correct 11 ms 748 KB Ok
43 Correct 12 ms 748 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9836 KB Ok
2 Correct 30 ms 9836 KB Ok
3 Correct 3 ms 876 KB Ok
4 Correct 3 ms 1772 KB Ok
5 Correct 3 ms 876 KB Ok
6 Correct 4 ms 2796 KB Ok
7 Correct 4 ms 876 KB Ok
8 Correct 4 ms 2284 KB Ok
9 Correct 3 ms 1004 KB Ok
10 Correct 3 ms 1260 KB Ok
11 Correct 2 ms 876 KB Ok
12 Correct 3 ms 748 KB Ok
13 Correct 16 ms 5120 KB Ok
14 Correct 17 ms 5100 KB Ok
15 Correct 12 ms 5100 KB Ok
16 Correct 17 ms 5228 KB Ok
17 Correct 14 ms 5100 KB Ok
18 Correct 18 ms 5228 KB Ok
19 Correct 30 ms 5868 KB Ok
20 Correct 19 ms 5484 KB Ok
21 Correct 35 ms 5996 KB Ok
22 Correct 22 ms 5612 KB Ok
23 Correct 16 ms 9836 KB Ok
24 Correct 34 ms 9836 KB Ok
25 Correct 22 ms 9836 KB Ok
26 Correct 19 ms 9836 KB Ok
27 Correct 11 ms 3564 KB Ok
28 Correct 11 ms 5100 KB Ok
29 Correct 8 ms 2284 KB Ok
30 Correct 11 ms 5100 KB Ok
31 Correct 12 ms 5100 KB Ok
32 Correct 15 ms 9836 KB Ok
33 Correct 15 ms 9836 KB Ok
34 Correct 4 ms 492 KB Ok
35 Correct 5 ms 492 KB Ok
36 Correct 5 ms 492 KB Ok
37 Correct 4 ms 492 KB Ok
38 Correct 4 ms 620 KB Ok
39 Correct 4 ms 492 KB Ok
40 Correct 4 ms 876 KB Ok
41 Correct 4 ms 492 KB Ok
42 Correct 6 ms 492 KB Ok
43 Correct 5 ms 492 KB Ok
44 Correct 12 ms 748 KB Ok
45 Correct 13 ms 748 KB Ok
46 Correct 11 ms 748 KB Ok
47 Correct 12 ms 748 KB Ok
48 Correct 11 ms 748 KB Ok
49 Correct 10 ms 748 KB Ok
50 Correct 12 ms 748 KB Ok
51 Correct 12 ms 748 KB Ok
52 Correct 11 ms 748 KB Ok
53 Correct 12 ms 748 KB Ok
54 Correct 113 ms 2916 KB Ok
55 Correct 130 ms 3428 KB Ok
56 Correct 121 ms 3300 KB Ok
57 Correct 98 ms 2672 KB Ok
58 Correct 119 ms 2916 KB Ok
59 Correct 115 ms 2532 KB Ok
60 Correct 99 ms 2404 KB Ok
61 Correct 97 ms 2532 KB Ok
62 Correct 142 ms 3300 KB Ok
63 Correct 109 ms 2660 KB Ok
64 Correct 135 ms 3300 KB Ok
65 Correct 140 ms 3044 KB Ok
66 Correct 109 ms 2796 KB Ok
67 Correct 95 ms 2660 KB Ok
68 Correct 115 ms 2788 KB Ok
69 Correct 319 ms 12004 KB Ok
70 Correct 388 ms 12648 KB Ok
71 Correct 308 ms 12260 KB Ok
72 Correct 349 ms 12132 KB Ok
73 Correct 317 ms 12032 KB Ok
74 Correct 293 ms 11852 KB Ok
75 Correct 286 ms 11492 KB Ok
76 Correct 361 ms 12516 KB Ok
77 Correct 276 ms 11524 KB Ok
78 Correct 361 ms 12004 KB Ok
79 Correct 324 ms 12284 KB Ok
80 Correct 309 ms 12260 KB Ok
81 Correct 324 ms 12132 KB Ok
82 Correct 319 ms 12132 KB Ok
83 Correct 300 ms 11748 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9836 KB Ok
2 Correct 30 ms 9836 KB Ok
3 Correct 3 ms 876 KB Ok
4 Correct 3 ms 1772 KB Ok
5 Correct 3 ms 876 KB Ok
6 Correct 4 ms 2796 KB Ok
7 Correct 4 ms 876 KB Ok
8 Correct 4 ms 2284 KB Ok
9 Correct 3 ms 1004 KB Ok
10 Correct 3 ms 1260 KB Ok
11 Correct 2 ms 876 KB Ok
12 Correct 3 ms 748 KB Ok
13 Correct 16 ms 5120 KB Ok
14 Correct 17 ms 5100 KB Ok
15 Correct 12 ms 5100 KB Ok
16 Correct 17 ms 5228 KB Ok
17 Correct 14 ms 5100 KB Ok
18 Correct 18 ms 5228 KB Ok
19 Correct 30 ms 5868 KB Ok
20 Correct 19 ms 5484 KB Ok
21 Correct 35 ms 5996 KB Ok
22 Correct 22 ms 5612 KB Ok
23 Correct 16 ms 9836 KB Ok
24 Correct 34 ms 9836 KB Ok
25 Correct 22 ms 9836 KB Ok
26 Correct 19 ms 9836 KB Ok
27 Correct 11 ms 3564 KB Ok
28 Correct 11 ms 5100 KB Ok
29 Correct 8 ms 2284 KB Ok
30 Correct 11 ms 5100 KB Ok
31 Correct 12 ms 5100 KB Ok
32 Correct 15 ms 9836 KB Ok
33 Correct 15 ms 9836 KB Ok
34 Correct 11 ms 3564 KB Ok
35 Correct 7 ms 1772 KB Ok
36 Correct 5 ms 1132 KB Ok
37 Correct 4 ms 1004 KB Ok
38 Correct 4 ms 876 KB Ok
39 Correct 268 ms 12384 KB Ok
40 Correct 266 ms 13664 KB Ok
41 Correct 469 ms 16352 KB Ok
42 Correct 347 ms 14424 KB Ok
43 Correct 188 ms 7396 KB Ok
44 Correct 348 ms 14944 KB Ok
45 Correct 4 ms 492 KB Ok
46 Correct 5 ms 492 KB Ok
47 Correct 5 ms 492 KB Ok
48 Correct 4 ms 492 KB Ok
49 Correct 4 ms 620 KB Ok
50 Correct 4 ms 492 KB Ok
51 Correct 4 ms 876 KB Ok
52 Correct 4 ms 492 KB Ok
53 Correct 6 ms 492 KB Ok
54 Correct 5 ms 492 KB Ok
55 Correct 12 ms 748 KB Ok
56 Correct 13 ms 748 KB Ok
57 Correct 11 ms 748 KB Ok
58 Correct 12 ms 748 KB Ok
59 Correct 11 ms 748 KB Ok
60 Correct 10 ms 748 KB Ok
61 Correct 12 ms 748 KB Ok
62 Correct 12 ms 748 KB Ok
63 Correct 11 ms 748 KB Ok
64 Correct 12 ms 748 KB Ok
65 Correct 113 ms 2916 KB Ok
66 Correct 130 ms 3428 KB Ok
67 Correct 121 ms 3300 KB Ok
68 Correct 98 ms 2672 KB Ok
69 Correct 119 ms 2916 KB Ok
70 Correct 115 ms 2532 KB Ok
71 Correct 99 ms 2404 KB Ok
72 Correct 97 ms 2532 KB Ok
73 Correct 142 ms 3300 KB Ok
74 Correct 109 ms 2660 KB Ok
75 Correct 135 ms 3300 KB Ok
76 Correct 140 ms 3044 KB Ok
77 Correct 109 ms 2796 KB Ok
78 Correct 95 ms 2660 KB Ok
79 Correct 115 ms 2788 KB Ok
80 Correct 319 ms 12004 KB Ok
81 Correct 388 ms 12648 KB Ok
82 Correct 308 ms 12260 KB Ok
83 Correct 349 ms 12132 KB Ok
84 Correct 317 ms 12032 KB Ok
85 Correct 293 ms 11852 KB Ok
86 Correct 286 ms 11492 KB Ok
87 Correct 361 ms 12516 KB Ok
88 Correct 276 ms 11524 KB Ok
89 Correct 361 ms 12004 KB Ok
90 Correct 324 ms 12284 KB Ok
91 Correct 309 ms 12260 KB Ok
92 Correct 324 ms 12132 KB Ok
93 Correct 319 ms 12132 KB Ok
94 Correct 300 ms 11748 KB Ok
95 Correct 297 ms 6752 KB Ok
96 Correct 437 ms 9052 KB Ok
97 Correct 407 ms 7900 KB Ok
98 Correct 298 ms 7004 KB Ok
99 Correct 367 ms 7516 KB Ok
100 Correct 371 ms 7548 KB Ok
101 Correct 384 ms 8028 KB Ok
102 Correct 383 ms 7900 KB Ok
103 Correct 376 ms 7900 KB Ok
104 Correct 441 ms 9180 KB Ok
105 Correct 398 ms 8924 KB Ok
106 Correct 356 ms 8540 KB Ok
107 Correct 417 ms 8540 KB Ok
108 Correct 453 ms 9436 KB Ok
109 Correct 373 ms 9052 KB Ok
110 Correct 1271 ms 47324 KB Ok
111 Correct 1596 ms 50204 KB Ok
112 Correct 1408 ms 50196 KB Ok
113 Correct 1481 ms 49504 KB Ok
114 Correct 1440 ms 51500 KB Ok
115 Correct 1459 ms 49144 KB Ok
116 Correct 1492 ms 50524 KB Ok
117 Correct 1566 ms 48936 KB Ok
118 Correct 1384 ms 49104 KB Ok
119 Correct 1661 ms 49372 KB Ok
120 Correct 1428 ms 48980 KB Ok
121 Correct 1339 ms 47452 KB Ok
122 Correct 1474 ms 50160 KB Ok
123 Correct 1652 ms 50388 KB Ok
124 Correct 1216 ms 47836 KB Ok
125 Correct 1451 ms 32632 KB Ok