oj.uz

Submission #386852

# Submission time Handle Problem Language Result Execution time Memory
386852 2021-04-07T13:39:25 Z vanic Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 71224 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;
//	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();
		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:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 19180 KB Ok
2 Correct 45 ms 19208 KB Ok
3 Correct 18 ms 10220 KB Ok
4 Correct 19 ms 11116 KB Ok
5 Correct 18 ms 10220 KB Ok
6 Correct 20 ms 12140 KB Ok
7 Correct 18 ms 10220 KB Ok
8 Correct 19 ms 11628 KB Ok
9 Correct 20 ms 10348 KB Ok
10 Correct 19 ms 10732 KB Ok
11 Correct 18 ms 10220 KB Ok
12 Correct 18 ms 10092 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 14444 KB Ok
2 Correct 33 ms 14444 KB Ok
3 Correct 33 ms 14444 KB Ok
4 Correct 33 ms 14572 KB Ok
5 Correct 29 ms 14444 KB Ok
6 Correct 33 ms 14700 KB Ok
7 Correct 52 ms 15616 KB Ok
8 Correct 35 ms 14956 KB Ok
9 Correct 57 ms 15596 KB Ok
10 Correct 40 ms 15212 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 19180 KB Ok
2 Correct 47 ms 19196 KB Ok
3 Correct 36 ms 19180 KB Ok
4 Correct 34 ms 19180 KB Ok
5 Correct 27 ms 12908 KB Ok
6 Correct 28 ms 14444 KB Ok
7 Correct 23 ms 11628 KB Ok
8 Correct 26 ms 14444 KB Ok
9 Correct 26 ms 14444 KB Ok
10 Correct 32 ms 19308 KB Ok
11 Correct 32 ms 19132 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12908 KB Ok
2 Correct 23 ms 11116 KB Ok
3 Correct 21 ms 10604 KB Ok
4 Correct 21 ms 10348 KB Ok
5 Correct 19 ms 10220 KB Ok
6 Correct 341 ms 26984 KB Ok
7 Correct 322 ms 32100 KB Ok
8 Correct 588 ms 34532 KB Ok
9 Correct 455 ms 31464 KB Ok
10 Correct 266 ms 20964 KB Ok
11 Correct 442 ms 30304 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 19180 KB Ok
2 Correct 45 ms 19208 KB Ok
3 Correct 18 ms 10220 KB Ok
4 Correct 19 ms 11116 KB Ok
5 Correct 18 ms 10220 KB Ok
6 Correct 20 ms 12140 KB Ok
7 Correct 18 ms 10220 KB Ok
8 Correct 19 ms 11628 KB Ok
9 Correct 20 ms 10348 KB Ok
10 Correct 19 ms 10732 KB Ok
11 Correct 18 ms 10220 KB Ok
12 Correct 18 ms 10092 KB Ok
13 Correct 24 ms 19180 KB Ok
14 Correct 47 ms 19196 KB Ok
15 Correct 36 ms 19180 KB Ok
16 Correct 34 ms 19180 KB Ok
17 Correct 27 ms 12908 KB Ok
18 Correct 28 ms 14444 KB Ok
19 Correct 23 ms 11628 KB Ok
20 Correct 26 ms 14444 KB Ok
21 Correct 26 ms 14444 KB Ok
22 Correct 32 ms 19308 KB Ok
23 Correct 32 ms 19132 KB Ok
24 Correct 21 ms 9964 KB Ok
25 Correct 20 ms 9964 KB Ok
26 Correct 21 ms 9964 KB Ok
27 Correct 20 ms 9964 KB Ok
28 Correct 20 ms 10092 KB Ok
29 Correct 20 ms 10112 KB Ok
30 Correct 20 ms 10220 KB Ok
31 Correct 22 ms 9964 KB Ok
32 Correct 21 ms 10092 KB Ok
33 Correct 21 ms 9964 KB Ok
34 Correct 27 ms 10220 KB Ok
35 Correct 29 ms 10220 KB Ok
36 Correct 28 ms 10220 KB Ok
37 Correct 33 ms 10348 KB Ok
38 Correct 28 ms 10220 KB Ok
39 Correct 27 ms 10220 KB Ok
40 Correct 30 ms 10220 KB Ok
41 Correct 29 ms 10220 KB Ok
42 Correct 28 ms 10220 KB Ok
43 Correct 29 ms 10348 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 19180 KB Ok
2 Correct 45 ms 19208 KB Ok
3 Correct 18 ms 10220 KB Ok
4 Correct 19 ms 11116 KB Ok
5 Correct 18 ms 10220 KB Ok
6 Correct 20 ms 12140 KB Ok
7 Correct 18 ms 10220 KB Ok
8 Correct 19 ms 11628 KB Ok
9 Correct 20 ms 10348 KB Ok
10 Correct 19 ms 10732 KB Ok
11 Correct 18 ms 10220 KB Ok
12 Correct 18 ms 10092 KB Ok
13 Correct 35 ms 14444 KB Ok
14 Correct 33 ms 14444 KB Ok
15 Correct 33 ms 14444 KB Ok
16 Correct 33 ms 14572 KB Ok
17 Correct 29 ms 14444 KB Ok
18 Correct 33 ms 14700 KB Ok
19 Correct 52 ms 15616 KB Ok
20 Correct 35 ms 14956 KB Ok
21 Correct 57 ms 15596 KB Ok
22 Correct 40 ms 15212 KB Ok
23 Correct 24 ms 19180 KB Ok
24 Correct 47 ms 19196 KB Ok
25 Correct 36 ms 19180 KB Ok
26 Correct 34 ms 19180 KB Ok
27 Correct 27 ms 12908 KB Ok
28 Correct 28 ms 14444 KB Ok
29 Correct 23 ms 11628 KB Ok
30 Correct 26 ms 14444 KB Ok
31 Correct 26 ms 14444 KB Ok
32 Correct 32 ms 19308 KB Ok
33 Correct 32 ms 19132 KB Ok
34 Correct 21 ms 9964 KB Ok
35 Correct 20 ms 9964 KB Ok
36 Correct 21 ms 9964 KB Ok
37 Correct 20 ms 9964 KB Ok
38 Correct 20 ms 10092 KB Ok
39 Correct 20 ms 10112 KB Ok
40 Correct 20 ms 10220 KB Ok
41 Correct 22 ms 9964 KB Ok
42 Correct 21 ms 10092 KB Ok
43 Correct 21 ms 9964 KB Ok
44 Correct 27 ms 10220 KB Ok
45 Correct 29 ms 10220 KB Ok
46 Correct 28 ms 10220 KB Ok
47 Correct 33 ms 10348 KB Ok
48 Correct 28 ms 10220 KB Ok
49 Correct 27 ms 10220 KB Ok
50 Correct 30 ms 10220 KB Ok
51 Correct 29 ms 10220 KB Ok
52 Correct 28 ms 10220 KB Ok
53 Correct 29 ms 10348 KB Ok
54 Correct 170 ms 15168 KB Ok
55 Correct 190 ms 15336 KB Ok
56 Correct 181 ms 15460 KB Ok
57 Correct 143 ms 14436 KB Ok
58 Correct 175 ms 15076 KB Ok
59 Correct 171 ms 14464 KB Ok
60 Correct 150 ms 14180 KB Ok
61 Correct 150 ms 14692 KB Ok
62 Correct 209 ms 15368 KB Ok
63 Correct 161 ms 14692 KB Ok
64 Correct 195 ms 15332 KB Ok
65 Correct 192 ms 14956 KB Ok
66 Correct 160 ms 14820 KB Ok
67 Correct 148 ms 14564 KB Ok
68 Correct 171 ms 14948 KB Ok
69 Correct 484 ms 25936 KB Ok
70 Correct 488 ms 26600 KB Ok
71 Correct 453 ms 25764 KB Ok
72 Correct 472 ms 26216 KB Ok
73 Correct 456 ms 25076 KB Ok
74 Correct 442 ms 24684 KB Ok
75 Correct 415 ms 25068 KB Ok
76 Correct 489 ms 26004 KB Ok
77 Correct 424 ms 24172 KB Ok
78 Correct 488 ms 24428 KB Ok
79 Correct 471 ms 25392 KB Ok
80 Correct 494 ms 25816 KB Ok
81 Correct 463 ms 24680 KB Ok
82 Correct 527 ms 25320 KB Ok
83 Correct 499 ms 25064 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 19180 KB Ok
2 Correct 45 ms 19208 KB Ok
3 Correct 18 ms 10220 KB Ok
4 Correct 19 ms 11116 KB Ok
5 Correct 18 ms 10220 KB Ok
6 Correct 20 ms 12140 KB Ok
7 Correct 18 ms 10220 KB Ok
8 Correct 19 ms 11628 KB Ok
9 Correct 20 ms 10348 KB Ok
10 Correct 19 ms 10732 KB Ok
11 Correct 18 ms 10220 KB Ok
12 Correct 18 ms 10092 KB Ok
13 Correct 35 ms 14444 KB Ok
14 Correct 33 ms 14444 KB Ok
15 Correct 33 ms 14444 KB Ok
16 Correct 33 ms 14572 KB Ok
17 Correct 29 ms 14444 KB Ok
18 Correct 33 ms 14700 KB Ok
19 Correct 52 ms 15616 KB Ok
20 Correct 35 ms 14956 KB Ok
21 Correct 57 ms 15596 KB Ok
22 Correct 40 ms 15212 KB Ok
23 Correct 24 ms 19180 KB Ok
24 Correct 47 ms 19196 KB Ok
25 Correct 36 ms 19180 KB Ok
26 Correct 34 ms 19180 KB Ok
27 Correct 27 ms 12908 KB Ok
28 Correct 28 ms 14444 KB Ok
29 Correct 23 ms 11628 KB Ok
30 Correct 26 ms 14444 KB Ok
31 Correct 26 ms 14444 KB Ok
32 Correct 32 ms 19308 KB Ok
33 Correct 32 ms 19132 KB Ok
34 Correct 26 ms 12908 KB Ok
35 Correct 23 ms 11116 KB Ok
36 Correct 21 ms 10604 KB Ok
37 Correct 21 ms 10348 KB Ok
38 Correct 19 ms 10220 KB Ok
39 Correct 341 ms 26984 KB Ok
40 Correct 322 ms 32100 KB Ok
41 Correct 588 ms 34532 KB Ok
42 Correct 455 ms 31464 KB Ok
43 Correct 266 ms 20964 KB Ok
44 Correct 442 ms 30304 KB Ok
45 Correct 21 ms 9964 KB Ok
46 Correct 20 ms 9964 KB Ok
47 Correct 21 ms 9964 KB Ok
48 Correct 20 ms 9964 KB Ok
49 Correct 20 ms 10092 KB Ok
50 Correct 20 ms 10112 KB Ok
51 Correct 20 ms 10220 KB Ok
52 Correct 22 ms 9964 KB Ok
53 Correct 21 ms 10092 KB Ok
54 Correct 21 ms 9964 KB Ok
55 Correct 27 ms 10220 KB Ok
56 Correct 29 ms 10220 KB Ok
57 Correct 28 ms 10220 KB Ok
58 Correct 33 ms 10348 KB Ok
59 Correct 28 ms 10220 KB Ok
60 Correct 27 ms 10220 KB Ok
61 Correct 30 ms 10220 KB Ok
62 Correct 29 ms 10220 KB Ok
63 Correct 28 ms 10220 KB Ok
64 Correct 29 ms 10348 KB Ok
65 Correct 170 ms 15168 KB Ok
66 Correct 190 ms 15336 KB Ok
67 Correct 181 ms 15460 KB Ok
68 Correct 143 ms 14436 KB Ok
69 Correct 175 ms 15076 KB Ok
70 Correct 171 ms 14464 KB Ok
71 Correct 150 ms 14180 KB Ok
72 Correct 150 ms 14692 KB Ok
73 Correct 209 ms 15368 KB Ok
74 Correct 161 ms 14692 KB Ok
75 Correct 195 ms 15332 KB Ok
76 Correct 192 ms 14956 KB Ok
77 Correct 160 ms 14820 KB Ok
78 Correct 148 ms 14564 KB Ok
79 Correct 171 ms 14948 KB Ok
80 Correct 484 ms 25936 KB Ok
81 Correct 488 ms 26600 KB Ok
82 Correct 453 ms 25764 KB Ok
83 Correct 472 ms 26216 KB Ok
84 Correct 456 ms 25076 KB Ok
85 Correct 442 ms 24684 KB Ok
86 Correct 415 ms 25068 KB Ok
87 Correct 489 ms 26004 KB Ok
88 Correct 424 ms 24172 KB Ok
89 Correct 488 ms 24428 KB Ok
90 Correct 471 ms 25392 KB Ok
91 Correct 494 ms 25816 KB Ok
92 Correct 463 ms 24680 KB Ok
93 Correct 527 ms 25320 KB Ok
94 Correct 499 ms 25064 KB Ok
95 Correct 444 ms 23596 KB Ok
96 Correct 625 ms 29276 KB Ok
97 Correct 586 ms 25820 KB Ok
98 Correct 447 ms 26076 KB Ok
99 Correct 536 ms 25588 KB Ok
100 Correct 531 ms 25184 KB Ok
101 Correct 654 ms 27996 KB Ok
102 Correct 543 ms 26204 KB Ok
103 Correct 545 ms 26972 KB Ok
104 Correct 624 ms 28836 KB Ok
105 Correct 581 ms 29036 KB Ok
106 Correct 554 ms 29532 KB Ok
107 Correct 616 ms 28252 KB Ok
108 Correct 642 ms 29124 KB Ok
109 Correct 556 ms 30304 KB Ok
110 Execution timed out 2079 ms 71224 KB Time limit exceeded
111 Halted 0 ms 0 KB -