oj.uz

Submission #36964

# Submission time Handle Problem Language Result Execution time Memory
36964 2017-12-19T17:14:55 Z szawinis Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 4976 ms 49164 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+1, M = 1 << 10;

int n, a[N], k[N], cnt[N], res[N], trace[N], dp[M][M][11];
vector<int> ord;
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", a+i);
	for(int i = 1; i <= n; i++) scanf("%d", k+i);
	for(int x = 0; x < M; x++) cnt[x] = __builtin_popcount(x);
	for(int i = 1; i <= n; i++) {
		res[i] = 1;
		int pref = a[i] >> 10, suff = a[i] - (pref << 10);
		// fix pref & x, find optimal idx such that when AND with suff, produces bitcount == residue
		// note that pref & x must be a prefix of a[idx] by the algorithm's nature
		for(int x = 0; x < M; x++) {
			int residue = k[i] - cnt[pref & x];
			if(residue < 0 || residue > 10) continue;
			int idx = dp[x][suff][residue];
			if(res[idx] + 1 > res[i]) {
				res[i] = res[idx] + 1;
				trace[i] = idx;
			}
		}
		// fix suff & x, and update accordingly
		for(int x = 0; x < M; x++) {
			int new_suff = suff & x;
			if(res[i] > res[dp[pref][x][cnt[new_suff]]])
				dp[pref][x][cnt[new_suff]] = i;
		}
	}
	int idx = max_element(res+1, res+n+1) - res;
	for(int i = idx; i > 0; i = trace[i]) ord.push_back(i);
	reverse(ord.begin(), ord.end());
	printf("%d\n", res[idx]);
	for(int i: ord) printf("%d ", i);
}

Compilation message

subsequence.cpp: In function 'int main()':
subsequence.cpp:8:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
subsequence.cpp:9:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", a+i);
                                              ^
subsequence.cpp:10:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", k+i);
                                              ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49024 KB answer = 4
2 Correct 0 ms 49024 KB answer = 1
3 Correct 0 ms 49024 KB answer = 2
4 Correct 0 ms 49024 KB answer = 1
5 Correct 0 ms 49024 KB answer = 2
6 Correct 0 ms 49024 KB answer = 1
7 Correct 0 ms 49024 KB answer = 1
8 Correct 0 ms 49024 KB answer = 3
9 Correct 3 ms 49024 KB answer = 2
10 Correct 3 ms 49024 KB answer = 3
11 Correct 0 ms 49024 KB answer = 2
12 Correct 0 ms 49024 KB answer = 3
13 Correct 0 ms 49024 KB answer = 2
14 Correct 0 ms 49024 KB answer = 1
15 Correct 0 ms 49024 KB answer = 1
16 Correct 0 ms 49024 KB answer = 1
17 Correct 3 ms 49024 KB answer = 1
18 Correct 3 ms 49024 KB answer = 1
19 Correct 3 ms 49024 KB answer = 1
20 Correct 0 ms 49024 KB answer = 1
21 Correct 0 ms 49024 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49024 KB answer = 4
2 Correct 0 ms 49024 KB answer = 1
3 Correct 0 ms 49024 KB answer = 2
4 Correct 0 ms 49024 KB answer = 1
5 Correct 0 ms 49024 KB answer = 2
6 Correct 0 ms 49024 KB answer = 1
7 Correct 0 ms 49024 KB answer = 1
8 Correct 0 ms 49024 KB answer = 3
9 Correct 3 ms 49024 KB answer = 2
10 Correct 3 ms 49024 KB answer = 3
11 Correct 0 ms 49024 KB answer = 2
12 Correct 0 ms 49024 KB answer = 3
13 Correct 0 ms 49024 KB answer = 2
14 Correct 0 ms 49024 KB answer = 1
15 Correct 0 ms 49024 KB answer = 1
16 Correct 0 ms 49024 KB answer = 1
17 Correct 3 ms 49024 KB answer = 1
18 Correct 3 ms 49024 KB answer = 1
19 Correct 3 ms 49024 KB answer = 1
20 Correct 0 ms 49024 KB answer = 1
21 Correct 0 ms 49024 KB answer = 1
22 Correct 159 ms 49024 KB answer = 358
23 Correct 139 ms 49024 KB answer = 336
24 Correct 159 ms 49024 KB answer = 339
25 Correct 163 ms 49024 KB answer = 357
26 Correct 139 ms 49024 KB answer = 354
27 Correct 136 ms 49024 KB answer = 333
28 Correct 126 ms 49024 KB answer = 314
29 Correct 119 ms 49024 KB answer = 322
30 Correct 139 ms 49024 KB answer = 339
31 Correct 156 ms 49024 KB answer = 351
32 Correct 189 ms 49024 KB answer = 1
33 Correct 203 ms 49024 KB answer = 1
34 Correct 219 ms 49024 KB answer = 1
35 Correct 263 ms 49024 KB answer = 1
36 Correct 249 ms 49024 KB answer = 1
37 Correct 53 ms 49024 KB answer = 1
38 Correct 59 ms 49024 KB answer = 1
39 Correct 56 ms 49024 KB answer = 1
40 Correct 43 ms 49024 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49024 KB answer = 4
2 Correct 0 ms 49024 KB answer = 1
3 Correct 0 ms 49024 KB answer = 2
4 Correct 0 ms 49024 KB answer = 1
5 Correct 0 ms 49024 KB answer = 2
6 Correct 0 ms 49024 KB answer = 1
7 Correct 0 ms 49024 KB answer = 1
8 Correct 0 ms 49024 KB answer = 3
9 Correct 3 ms 49024 KB answer = 2
10 Correct 3 ms 49024 KB answer = 3
11 Correct 0 ms 49024 KB answer = 2
12 Correct 0 ms 49024 KB answer = 3
13 Correct 0 ms 49024 KB answer = 2
14 Correct 0 ms 49024 KB answer = 1
15 Correct 0 ms 49024 KB answer = 1
16 Correct 0 ms 49024 KB answer = 1
17 Correct 3 ms 49024 KB answer = 1
18 Correct 3 ms 49024 KB answer = 1
19 Correct 3 ms 49024 KB answer = 1
20 Correct 0 ms 49024 KB answer = 1
21 Correct 0 ms 49024 KB answer = 1
22 Correct 159 ms 49024 KB answer = 358
23 Correct 139 ms 49024 KB answer = 336
24 Correct 159 ms 49024 KB answer = 339
25 Correct 163 ms 49024 KB answer = 357
26 Correct 139 ms 49024 KB answer = 354
27 Correct 136 ms 49024 KB answer = 333
28 Correct 126 ms 49024 KB answer = 314
29 Correct 119 ms 49024 KB answer = 322
30 Correct 139 ms 49024 KB answer = 339
31 Correct 156 ms 49024 KB answer = 351
32 Correct 189 ms 49024 KB answer = 1
33 Correct 203 ms 49024 KB answer = 1
34 Correct 219 ms 49024 KB answer = 1
35 Correct 263 ms 49024 KB answer = 1
36 Correct 249 ms 49024 KB answer = 1
37 Correct 53 ms 49024 KB answer = 1
38 Correct 59 ms 49024 KB answer = 1
39 Correct 56 ms 49024 KB answer = 1
40 Correct 43 ms 49024 KB answer = 1
41 Correct 776 ms 49164 KB answer = 6296
42 Correct 749 ms 49164 KB answer = 6267
43 Correct 746 ms 49164 KB answer = 6264
44 Correct 786 ms 49164 KB answer = 6384
45 Correct 729 ms 49164 KB answer = 6272
46 Correct 719 ms 49164 KB answer = 6177
47 Correct 679 ms 49164 KB answer = 6144
48 Correct 663 ms 49164 KB answer = 6272
49 Correct 726 ms 49164 KB answer = 6241
50 Correct 679 ms 49164 KB answer = 6169
51 Correct 419 ms 49024 KB answer = 1
52 Correct 366 ms 49024 KB answer = 1
53 Correct 346 ms 49024 KB answer = 1
54 Correct 366 ms 49024 KB answer = 1
55 Correct 366 ms 49024 KB answer = 1
56 Correct 679 ms 49024 KB answer = 1426
57 Correct 659 ms 49024 KB answer = 1427
58 Correct 766 ms 49024 KB answer = 1428
59 Correct 756 ms 49024 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49024 KB answer = 4
2 Correct 0 ms 49024 KB answer = 1
3 Correct 0 ms 49024 KB answer = 2
4 Correct 0 ms 49024 KB answer = 1
5 Correct 0 ms 49024 KB answer = 2
6 Correct 0 ms 49024 KB answer = 1
7 Correct 0 ms 49024 KB answer = 1
8 Correct 0 ms 49024 KB answer = 3
9 Correct 3 ms 49024 KB answer = 2
10 Correct 3 ms 49024 KB answer = 3
11 Correct 0 ms 49024 KB answer = 2
12 Correct 0 ms 49024 KB answer = 3
13 Correct 0 ms 49024 KB answer = 2
14 Correct 0 ms 49024 KB answer = 1
15 Correct 0 ms 49024 KB answer = 1
16 Correct 0 ms 49024 KB answer = 1
17 Correct 3 ms 49024 KB answer = 1
18 Correct 3 ms 49024 KB answer = 1
19 Correct 3 ms 49024 KB answer = 1
20 Correct 0 ms 49024 KB answer = 1
21 Correct 0 ms 49024 KB answer = 1
22 Correct 159 ms 49024 KB answer = 358
23 Correct 139 ms 49024 KB answer = 336
24 Correct 159 ms 49024 KB answer = 339
25 Correct 163 ms 49024 KB answer = 357
26 Correct 139 ms 49024 KB answer = 354
27 Correct 136 ms 49024 KB answer = 333
28 Correct 126 ms 49024 KB answer = 314
29 Correct 119 ms 49024 KB answer = 322
30 Correct 139 ms 49024 KB answer = 339
31 Correct 156 ms 49024 KB answer = 351
32 Correct 189 ms 49024 KB answer = 1
33 Correct 203 ms 49024 KB answer = 1
34 Correct 219 ms 49024 KB answer = 1
35 Correct 263 ms 49024 KB answer = 1
36 Correct 249 ms 49024 KB answer = 1
37 Correct 53 ms 49024 KB answer = 1
38 Correct 59 ms 49024 KB answer = 1
39 Correct 56 ms 49024 KB answer = 1
40 Correct 43 ms 49024 KB answer = 1
41 Correct 776 ms 49164 KB answer = 6296
42 Correct 749 ms 49164 KB answer = 6267
43 Correct 746 ms 49164 KB answer = 6264
44 Correct 786 ms 49164 KB answer = 6384
45 Correct 729 ms 49164 KB answer = 6272
46 Correct 719 ms 49164 KB answer = 6177
47 Correct 679 ms 49164 KB answer = 6144
48 Correct 663 ms 49164 KB answer = 6272
49 Correct 726 ms 49164 KB answer = 6241
50 Correct 679 ms 49164 KB answer = 6169
51 Correct 419 ms 49024 KB answer = 1
52 Correct 366 ms 49024 KB answer = 1
53 Correct 346 ms 49024 KB answer = 1
54 Correct 366 ms 49024 KB answer = 1
55 Correct 366 ms 49024 KB answer = 1
56 Correct 679 ms 49024 KB answer = 1426
57 Correct 659 ms 49024 KB answer = 1427
58 Correct 766 ms 49024 KB answer = 1428
59 Correct 756 ms 49024 KB answer = 1427
60 Correct 3229 ms 49164 KB answer = 7034
61 Correct 3193 ms 49164 KB answer = 7045
62 Correct 3119 ms 49164 KB answer = 7147
63 Correct 3216 ms 49164 KB answer = 7038
64 Correct 3299 ms 49164 KB answer = 7169
65 Correct 3349 ms 49164 KB answer = 6735
66 Correct 3216 ms 49164 KB answer = 6713
67 Correct 2976 ms 49164 KB answer = 6748
68 Correct 3023 ms 49164 KB answer = 6607
69 Correct 3079 ms 49164 KB answer = 6722
70 Correct 4733 ms 49024 KB answer = 1
71 Correct 4683 ms 49024 KB answer = 1
72 Correct 4976 ms 49024 KB answer = 1
73 Correct 4626 ms 49024 KB answer = 1
74 Correct 4653 ms 49024 KB answer = 1
75 Correct 1476 ms 49024 KB answer = 1
76 Correct 1319 ms 49024 KB answer = 1
77 Correct 1349 ms 49024 KB answer = 1
78 Correct 1406 ms 49024 KB answer = 1
79 Correct 1853 ms 49024 KB answer = 21
80 Correct 1776 ms 49024 KB answer = 7
81 Correct 2369 ms 49024 KB answer = 3
82 Correct 2473 ms 49024 KB answer = 2
83 Correct 1916 ms 49024 KB answer = 1
84 Correct 1463 ms 49024 KB answer = 1
85 Correct 1336 ms 49024 KB answer = 1
86 Correct 1509 ms 49024 KB answer = 11
87 Correct 2283 ms 49024 KB answer = 11
88 Correct 2636 ms 49024 KB answer = 6
89 Correct 2529 ms 49024 KB answer = 4
90 Correct 1839 ms 49024 KB answer = 2
91 Correct 1649 ms 49024 KB answer = 2
92 Correct 1466 ms 49024 KB answer = 2
93 Correct 3229 ms 49164 KB answer = 7211
94 Correct 3103 ms 49164 KB answer = 7032
95 Correct 3293 ms 49164 KB answer = 7092
96 Correct 4103 ms 49164 KB answer = 14167
97 Correct 3666 ms 49164 KB answer = 14159
98 Correct 4029 ms 49164 KB answer = 14125
99 Correct 3923 ms 49164 KB answer = 14121
100 Correct 3866 ms 49164 KB answer = 14010
101 Correct 3896 ms 49164 KB answer = 13976
102 Correct 1413 ms 49024 KB answer = 3
103 Correct 1703 ms 49024 KB answer = 2
104 Correct 1953 ms 49024 KB answer = 3
105 Correct 1196 ms 49024 KB answer = 2
106 Correct 1199 ms 49024 KB answer = 3
107 Correct 1483 ms 49024 KB answer = 4
108 Correct 1393 ms 49024 KB answer = 5
109 Correct 1018 ms 49024 KB answer = 8
110 Correct 723 ms 49024 KB answer = 22
111 Correct 3046 ms 49164 KB answer = 6760
112 Correct 3136 ms 49164 KB answer = 6788
113 Correct 2973 ms 49164 KB answer = 6632