oj.uz

Submission #633909

# Submission time Handle Problem Language Result Execution time Memory
633909 2022-08-23T12:44:37 Z lovrot Nice sequence (IZhO18_sequence) C++11
100 / 100
 1110 ms 46412 KB 
#include <bits/stdc++.h> 

#define pb push_back 
#define X first
#define Y second
#define pii pair<int, int>

using namespace std;

const int N = 4 * 1e5 + 10;

int t, n, m, p[N], ans, pos;
int bio[N], ts[N], cookie;

bool cycp(int u){
	if(bio[u] == cookie + 1 || bio[u] == cookie) return bio[u] == cookie;
	bio[u] = cookie;
	if(u - m >= 0 && cycp(u - m)) return true;
	if(u + n <= ans && cycp(u + n)) return true;
	bio[u] = cookie + 1;
	return false;
}

void topSort(int u){ 
	ts[u] = cookie;
	if(u - m >= 0){
		if(ts[u - m] != cookie) topSort(u - m);
	}
	if(u + n <= ans){ 
		if(ts[u + n] != cookie) topSort(u + n);
	}
	p[u] = ++pos;
}

void output(){ 
	for(int i = 0; i <= ans; i++)
		if(ts[i] != cookie) topSort(i);

	printf("%d\n", ans);
	for(int i = 1; i <= ans; i++) 
		printf("%d ", (p[i] - p[0]) - (p[i - 1] - p[0]));
	printf("\n");
}

bool probaj(){ 
	pos = -1;
	cookie += 2;

	for(int i = 0; i <= ans; i++){ 
		if(bio[i] != cookie + 1 && cycp(i)) return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	
	scanf("%d", &t);

	while(t--){ 
		scanf("%d %d", &n, &m);

		int lo = 0, hi = (n + m) + 1;
		while(hi - lo > 1){ 
			int mi = (lo + hi) / 2;
			ans = mi;
			if(probaj())
				lo = mi;
			else 
				hi = mi;
		}
		ans = lo;
		probaj();
		output();
	}
	return 0;
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 3 ms 416 KB Ok
7 Correct 15 ms 1100 KB Ok
8 Correct 7 ms 676 KB Ok
9 Correct 17 ms 1192 KB Ok
10 Correct 10 ms 848 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 169 ms 10440 KB Ok
7 Correct 158 ms 10932 KB Ok
8 Correct 303 ms 13884 KB Ok
9 Correct 208 ms 12184 KB Ok
10 Correct 116 ms 6072 KB Ok
11 Correct 182 ms 12256 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 1 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 0 ms 340 KB Ok
18 Correct 0 ms 340 KB Ok
19 Correct 1 ms 340 KB Ok
20 Correct 1 ms 340 KB Ok
21 Correct 0 ms 340 KB Ok
22 Correct 0 ms 340 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 3 ms 340 KB Ok
25 Correct 2 ms 340 KB Ok
26 Correct 3 ms 340 KB Ok
27 Correct 3 ms 340 KB Ok
28 Correct 2 ms 340 KB Ok
29 Correct 2 ms 340 KB Ok
30 Correct 2 ms 340 KB Ok
31 Correct 3 ms 340 KB Ok
32 Correct 3 ms 340 KB Ok
33 Correct 2 ms 340 KB Ok
34 Correct 6 ms 596 KB Ok
35 Correct 8 ms 596 KB Ok
36 Correct 6 ms 548 KB Ok
37 Correct 6 ms 560 KB Ok
38 Correct 8 ms 656 KB Ok
39 Correct 6 ms 596 KB Ok
40 Correct 7 ms 568 KB Ok
41 Correct 6 ms 596 KB Ok
42 Correct 6 ms 596 KB Ok
43 Correct 7 ms 596 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 0 ms 340 KB Ok
18 Correct 3 ms 416 KB Ok
19 Correct 15 ms 1100 KB Ok
20 Correct 7 ms 676 KB Ok
21 Correct 17 ms 1192 KB Ok
22 Correct 10 ms 848 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 1 ms 340 KB Ok
25 Correct 0 ms 340 KB Ok
26 Correct 0 ms 340 KB Ok
27 Correct 0 ms 340 KB Ok
28 Correct 0 ms 340 KB Ok
29 Correct 1 ms 340 KB Ok
30 Correct 1 ms 340 KB Ok
31 Correct 0 ms 340 KB Ok
32 Correct 0 ms 340 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 3 ms 340 KB Ok
35 Correct 2 ms 340 KB Ok
36 Correct 3 ms 340 KB Ok
37 Correct 3 ms 340 KB Ok
38 Correct 2 ms 340 KB Ok
39 Correct 2 ms 340 KB Ok
40 Correct 2 ms 340 KB Ok
41 Correct 3 ms 340 KB Ok
42 Correct 3 ms 340 KB Ok
43 Correct 2 ms 340 KB Ok
44 Correct 6 ms 596 KB Ok
45 Correct 8 ms 596 KB Ok
46 Correct 6 ms 548 KB Ok
47 Correct 6 ms 560 KB Ok
48 Correct 8 ms 656 KB Ok
49 Correct 6 ms 596 KB Ok
50 Correct 7 ms 568 KB Ok
51 Correct 6 ms 596 KB Ok
52 Correct 6 ms 596 KB Ok
53 Correct 7 ms 596 KB Ok
54 Correct 103 ms 2972 KB Ok
55 Correct 119 ms 3280 KB Ok
56 Correct 125 ms 3332 KB Ok
57 Correct 83 ms 2608 KB Ok
58 Correct 100 ms 2772 KB Ok
59 Correct 91 ms 2588 KB Ok
60 Correct 84 ms 2376 KB Ok
61 Correct 82 ms 2636 KB Ok
62 Correct 109 ms 3148 KB Ok
63 Correct 91 ms 2728 KB Ok
64 Correct 122 ms 3408 KB Ok
65 Correct 102 ms 3008 KB Ok
66 Correct 91 ms 2756 KB Ok
67 Correct 92 ms 2776 KB Ok
68 Correct 95 ms 2892 KB Ok
69 Correct 241 ms 10580 KB Ok
70 Correct 244 ms 11160 KB Ok
71 Correct 229 ms 10616 KB Ok
72 Correct 235 ms 10456 KB Ok
73 Correct 244 ms 10652 KB Ok
74 Correct 217 ms 10444 KB Ok
75 Correct 233 ms 10060 KB Ok
76 Correct 253 ms 10808 KB Ok
77 Correct 229 ms 10040 KB Ok
78 Correct 260 ms 10576 KB Ok
79 Correct 263 ms 10768 KB Ok
80 Correct 238 ms 10952 KB Ok
81 Correct 244 ms 10704 KB Ok
82 Correct 225 ms 10680 KB Ok
83 Correct 222 ms 10216 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 0 ms 340 KB Ok
18 Correct 3 ms 416 KB Ok
19 Correct 15 ms 1100 KB Ok
20 Correct 7 ms 676 KB Ok
21 Correct 17 ms 1192 KB Ok
22 Correct 10 ms 848 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 1 ms 340 KB Ok
25 Correct 0 ms 340 KB Ok
26 Correct 0 ms 340 KB Ok
27 Correct 0 ms 340 KB Ok
28 Correct 0 ms 340 KB Ok
29 Correct 1 ms 340 KB Ok
30 Correct 1 ms 340 KB Ok
31 Correct 0 ms 340 KB Ok
32 Correct 0 ms 340 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 1 ms 340 KB Ok
35 Correct 0 ms 340 KB Ok
36 Correct 0 ms 340 KB Ok
37 Correct 1 ms 340 KB Ok
38 Correct 0 ms 340 KB Ok
39 Correct 169 ms 10440 KB Ok
40 Correct 158 ms 10932 KB Ok
41 Correct 303 ms 13884 KB Ok
42 Correct 208 ms 12184 KB Ok
43 Correct 116 ms 6072 KB Ok
44 Correct 182 ms 12256 KB Ok
45 Correct 3 ms 340 KB Ok
46 Correct 2 ms 340 KB Ok
47 Correct 3 ms 340 KB Ok
48 Correct 3 ms 340 KB Ok
49 Correct 2 ms 340 KB Ok
50 Correct 2 ms 340 KB Ok
51 Correct 2 ms 340 KB Ok
52 Correct 3 ms 340 KB Ok
53 Correct 3 ms 340 KB Ok
54 Correct 2 ms 340 KB Ok
55 Correct 6 ms 596 KB Ok
56 Correct 8 ms 596 KB Ok
57 Correct 6 ms 548 KB Ok
58 Correct 6 ms 560 KB Ok
59 Correct 8 ms 656 KB Ok
60 Correct 6 ms 596 KB Ok
61 Correct 7 ms 568 KB Ok
62 Correct 6 ms 596 KB Ok
63 Correct 6 ms 596 KB Ok
64 Correct 7 ms 596 KB Ok
65 Correct 103 ms 2972 KB Ok
66 Correct 119 ms 3280 KB Ok
67 Correct 125 ms 3332 KB Ok
68 Correct 83 ms 2608 KB Ok
69 Correct 100 ms 2772 KB Ok
70 Correct 91 ms 2588 KB Ok
71 Correct 84 ms 2376 KB Ok
72 Correct 82 ms 2636 KB Ok
73 Correct 109 ms 3148 KB Ok
74 Correct 91 ms 2728 KB Ok
75 Correct 122 ms 3408 KB Ok
76 Correct 102 ms 3008 KB Ok
77 Correct 91 ms 2756 KB Ok
78 Correct 92 ms 2776 KB Ok
79 Correct 95 ms 2892 KB Ok
80 Correct 241 ms 10580 KB Ok
81 Correct 244 ms 11160 KB Ok
82 Correct 229 ms 10616 KB Ok
83 Correct 235 ms 10456 KB Ok
84 Correct 244 ms 10652 KB Ok
85 Correct 217 ms 10444 KB Ok
86 Correct 233 ms 10060 KB Ok
87 Correct 253 ms 10808 KB Ok
88 Correct 229 ms 10040 KB Ok
89 Correct 260 ms 10576 KB Ok
90 Correct 263 ms 10768 KB Ok
91 Correct 238 ms 10952 KB Ok
92 Correct 244 ms 10704 KB Ok
93 Correct 225 ms 10680 KB Ok
94 Correct 222 ms 10216 KB Ok
95 Correct 289 ms 7328 KB Ok
96 Correct 357 ms 10020 KB Ok
97 Correct 367 ms 8780 KB Ok
98 Correct 251 ms 7972 KB Ok
99 Correct 315 ms 8352 KB Ok
100 Correct 325 ms 8252 KB Ok
101 Correct 339 ms 9032 KB Ok
102 Correct 340 ms 8616 KB Ok
103 Correct 322 ms 8884 KB Ok
104 Correct 412 ms 10164 KB Ok
105 Correct 352 ms 9876 KB Ok
106 Correct 301 ms 9760 KB Ok
107 Correct 364 ms 9452 KB Ok
108 Correct 411 ms 10208 KB Ok
109 Correct 334 ms 10268 KB Ok
110 Correct 1037 ms 42452 KB Ok
111 Correct 1078 ms 45236 KB Ok
112 Correct 1095 ms 45152 KB Ok
113 Correct 1110 ms 44388 KB Ok
114 Correct 1104 ms 46412 KB Ok
115 Correct 1088 ms 44264 KB Ok
116 Correct 1107 ms 45508 KB Ok
117 Correct 1097 ms 44188 KB Ok
118 Correct 1022 ms 44264 KB Ok
119 Correct 1093 ms 43956 KB Ok
120 Correct 1012 ms 44048 KB Ok
121 Correct 1047 ms 42408 KB Ok
122 Correct 1062 ms 44964 KB Ok
123 Correct 1069 ms 45312 KB Ok
124 Correct 1090 ms 42748 KB Ok
125 Correct 1049 ms 27508 KB Ok