oj.uz

Submission #36348

# Submission time Handle Problem Language Result Execution time Memory
36348 2017-12-08T01:19:51 Z ToMoClone Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 5686 ms 93444 KB 
/*input
5
5 3 5 3 5
10 1 20 1 20
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
 
const int N = 100005, M = 1 << 10;
int n, a[N], bitcount[N], trace[N], Bit[M];
pair<int, int> f[M][M][11], ans;
 
int pop_count(int v){
	v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
	return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
}
 
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", &bitcount[i]);
	for(int i = 0; i < M; ++i)
		Bit[i] = pop_count(i);
 
	for(int i = 1; i <= n; ++i){
		int pref = a[i] >> 10, suf = a[i] % M, cur = 1, save = 0;
		for(int mask = 0; mask < M; ++mask){
			int cnt = bitcount[i] - Bit[mask & pref];
			if(cnt < 0 || 10 < cnt) continue;

			if(cur < f[mask][suf][cnt].first + 1)
				cur = f[mask][suf][cnt].first + 1, save = f[mask][suf][cnt].second;
		}
		trace[i] = save;
 
		for(int mask = 0; mask < M; ++mask){
			int cnt = Bit[mask & suf];
			if(f[pref][mask][cnt].first < cur)
				f[pref][mask][cnt] = make_pair(cur, i);
		}
		if(ans.first < cur) ans = make_pair(cur, i);
	}
 
	vector<int> res;
	while(ans.second){
		res.push_back(ans.second);
		ans.second = trace[ans.second];
	}
	reverse(res.begin(), res.end());
 
	printf("%d\n", (int)res.size());
	for(int i = 0; i < (int)res.size(); ++i)
		printf("%s%d", i ? " " : "", res[i]);
}

Compilation message

subsequence.cpp: In function 'int pop_count(int)':
subsequence.cpp:17:13: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
             ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:21:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
subsequence.cpp:23:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^
subsequence.cpp:25:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &bitcount[i]);
                            ^

Subtask #1
7.0 / 7.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 93304 KB answer = 4
2 Correct 0 ms 93304 KB answer = 1
3 Correct 0 ms 93304 KB answer = 2
4 Correct 0 ms 93304 KB answer = 1
5 Correct 0 ms 93304 KB answer = 2
6 Correct 0 ms 93304 KB answer = 1
7 Correct 0 ms 93304 KB answer = 1
8 Correct 3 ms 93304 KB answer = 3
9 Correct 3 ms 93304 KB answer = 2
10 Correct 6 ms 93304 KB answer = 3
11 Correct 3 ms 93304 KB answer = 2
12 Correct 0 ms 93304 KB answer = 3
13 Correct 3 ms 93304 KB answer = 2
14 Correct 3 ms 93304 KB answer = 1
15 Correct 0 ms 93304 KB answer = 1
16 Correct 0 ms 93304 KB answer = 1
17 Correct 3 ms 93304 KB answer = 1
18 Correct 0 ms 93304 KB answer = 1
19 Correct 3 ms 93304 KB answer = 1
20 Correct 0 ms 93304 KB answer = 1
21 Correct 0 ms 93304 KB answer = 1
22 Correct 199 ms 93304 KB answer = 358
23 Correct 176 ms 93304 KB answer = 336
24 Correct 206 ms 93304 KB answer = 339
25 Correct 196 ms 93304 KB answer = 357
26 Correct 216 ms 93304 KB answer = 354
27 Correct 179 ms 93304 KB answer = 333
28 Correct 186 ms 93304 KB answer = 314
29 Correct 193 ms 93304 KB answer = 322
30 Correct 199 ms 93304 KB answer = 339
31 Correct 183 ms 93304 KB answer = 351
32 Correct 246 ms 93304 KB answer = 1
33 Correct 223 ms 93304 KB answer = 1
34 Correct 236 ms 93304 KB answer = 1
35 Correct 243 ms 93304 KB answer = 1
36 Correct 239 ms 93304 KB answer = 1
37 Correct 56 ms 93304 KB answer = 1
38 Correct 56 ms 93304 KB answer = 1
39 Correct 56 ms 93304 KB answer = 1
40 Correct 66 ms 93304 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 93304 KB answer = 4
2 Correct 0 ms 93304 KB answer = 1
3 Correct 0 ms 93304 KB answer = 2
4 Correct 0 ms 93304 KB answer = 1
5 Correct 0 ms 93304 KB answer = 2
6 Correct 0 ms 93304 KB answer = 1
7 Correct 0 ms 93304 KB answer = 1
8 Correct 3 ms 93304 KB answer = 3
9 Correct 3 ms 93304 KB answer = 2
10 Correct 6 ms 93304 KB answer = 3
11 Correct 3 ms 93304 KB answer = 2
12 Correct 0 ms 93304 KB answer = 3
13 Correct 3 ms 93304 KB answer = 2
14 Correct 3 ms 93304 KB answer = 1
15 Correct 0 ms 93304 KB answer = 1
16 Correct 0 ms 93304 KB answer = 1
17 Correct 3 ms 93304 KB answer = 1
18 Correct 0 ms 93304 KB answer = 1
19 Correct 3 ms 93304 KB answer = 1
20 Correct 0 ms 93304 KB answer = 1
21 Correct 0 ms 93304 KB answer = 1
22 Correct 199 ms 93304 KB answer = 358
23 Correct 176 ms 93304 KB answer = 336
24 Correct 206 ms 93304 KB answer = 339
25 Correct 196 ms 93304 KB answer = 357
26 Correct 216 ms 93304 KB answer = 354
27 Correct 179 ms 93304 KB answer = 333
28 Correct 186 ms 93304 KB answer = 314
29 Correct 193 ms 93304 KB answer = 322
30 Correct 199 ms 93304 KB answer = 339
31 Correct 183 ms 93304 KB answer = 351
32 Correct 246 ms 93304 KB answer = 1
33 Correct 223 ms 93304 KB answer = 1
34 Correct 236 ms 93304 KB answer = 1
35 Correct 243 ms 93304 KB answer = 1
36 Correct 239 ms 93304 KB answer = 1
37 Correct 56 ms 93304 KB answer = 1
38 Correct 56 ms 93304 KB answer = 1
39 Correct 56 ms 93304 KB answer = 1
40 Correct 66 ms 93304 KB answer = 1
41 Correct 986 ms 93444 KB answer = 6296
42 Correct 1033 ms 93444 KB answer = 6267
43 Correct 1063 ms 93444 KB answer = 6264
44 Correct 933 ms 93444 KB answer = 6384
45 Correct 989 ms 93444 KB answer = 6272
46 Correct 943 ms 93444 KB answer = 6177
47 Correct 943 ms 93444 KB answer = 6144
48 Correct 953 ms 93444 KB answer = 6272
49 Correct 1026 ms 93444 KB answer = 6241
50 Correct 899 ms 93444 KB answer = 6169
51 Correct 326 ms 93304 KB answer = 1
52 Correct 333 ms 93304 KB answer = 1
53 Correct 309 ms 93304 KB answer = 1
54 Correct 316 ms 93304 KB answer = 1
55 Correct 329 ms 93304 KB answer = 1
56 Correct 823 ms 93304 KB answer = 1426
57 Correct 843 ms 93304 KB answer = 1427
58 Correct 876 ms 93304 KB answer = 1428
59 Correct 816 ms 93304 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 93304 KB answer = 4
2 Correct 0 ms 93304 KB answer = 1
3 Correct 0 ms 93304 KB answer = 2
4 Correct 0 ms 93304 KB answer = 1
5 Correct 0 ms 93304 KB answer = 2
6 Correct 0 ms 93304 KB answer = 1
7 Correct 0 ms 93304 KB answer = 1
8 Correct 3 ms 93304 KB answer = 3
9 Correct 3 ms 93304 KB answer = 2
10 Correct 6 ms 93304 KB answer = 3
11 Correct 3 ms 93304 KB answer = 2
12 Correct 0 ms 93304 KB answer = 3
13 Correct 3 ms 93304 KB answer = 2
14 Correct 3 ms 93304 KB answer = 1
15 Correct 0 ms 93304 KB answer = 1
16 Correct 0 ms 93304 KB answer = 1
17 Correct 3 ms 93304 KB answer = 1
18 Correct 0 ms 93304 KB answer = 1
19 Correct 3 ms 93304 KB answer = 1
20 Correct 0 ms 93304 KB answer = 1
21 Correct 0 ms 93304 KB answer = 1
22 Correct 199 ms 93304 KB answer = 358
23 Correct 176 ms 93304 KB answer = 336
24 Correct 206 ms 93304 KB answer = 339
25 Correct 196 ms 93304 KB answer = 357
26 Correct 216 ms 93304 KB answer = 354
27 Correct 179 ms 93304 KB answer = 333
28 Correct 186 ms 93304 KB answer = 314
29 Correct 193 ms 93304 KB answer = 322
30 Correct 199 ms 93304 KB answer = 339
31 Correct 183 ms 93304 KB answer = 351
32 Correct 246 ms 93304 KB answer = 1
33 Correct 223 ms 93304 KB answer = 1
34 Correct 236 ms 93304 KB answer = 1
35 Correct 243 ms 93304 KB answer = 1
36 Correct 239 ms 93304 KB answer = 1
37 Correct 56 ms 93304 KB answer = 1
38 Correct 56 ms 93304 KB answer = 1
39 Correct 56 ms 93304 KB answer = 1
40 Correct 66 ms 93304 KB answer = 1
41 Correct 986 ms 93444 KB answer = 6296
42 Correct 1033 ms 93444 KB answer = 6267
43 Correct 1063 ms 93444 KB answer = 6264
44 Correct 933 ms 93444 KB answer = 6384
45 Correct 989 ms 93444 KB answer = 6272
46 Correct 943 ms 93444 KB answer = 6177
47 Correct 943 ms 93444 KB answer = 6144
48 Correct 953 ms 93444 KB answer = 6272
49 Correct 1026 ms 93444 KB answer = 6241
50 Correct 899 ms 93444 KB answer = 6169
51 Correct 326 ms 93304 KB answer = 1
52 Correct 333 ms 93304 KB answer = 1
53 Correct 309 ms 93304 KB answer = 1
54 Correct 316 ms 93304 KB answer = 1
55 Correct 329 ms 93304 KB answer = 1
56 Correct 823 ms 93304 KB answer = 1426
57 Correct 843 ms 93304 KB answer = 1427
58 Correct 876 ms 93304 KB answer = 1428
59 Correct 816 ms 93304 KB answer = 1427
60 Correct 3879 ms 93444 KB answer = 7034
61 Correct 3713 ms 93444 KB answer = 7045
62 Correct 4136 ms 93444 KB answer = 7147
63 Correct 3946 ms 93444 KB answer = 7038
64 Correct 3796 ms 93444 KB answer = 7169
65 Correct 3826 ms 93444 KB answer = 6735
66 Correct 3679 ms 93444 KB answer = 6713
67 Correct 3879 ms 93444 KB answer = 6748
68 Correct 4189 ms 93444 KB answer = 6607
69 Correct 3959 ms 93444 KB answer = 6722
70 Correct 5616 ms 93304 KB answer = 1
71 Correct 5686 ms 93304 KB answer = 1
72 Correct 5603 ms 93304 KB answer = 1
73 Correct 5443 ms 93304 KB answer = 1
74 Correct 5343 ms 93304 KB answer = 1
75 Correct 1759 ms 93304 KB answer = 1
76 Correct 1473 ms 93304 KB answer = 1
77 Correct 1639 ms 93304 KB answer = 1
78 Correct 1773 ms 93304 KB answer = 1
79 Correct 2163 ms 93304 KB answer = 21
80 Correct 2516 ms 93304 KB answer = 7
81 Correct 2953 ms 93304 KB answer = 3
82 Correct 2789 ms 93304 KB answer = 2
83 Correct 2239 ms 93304 KB answer = 1
84 Correct 1836 ms 93304 KB answer = 1
85 Correct 1619 ms 93304 KB answer = 1
86 Correct 2256 ms 93304 KB answer = 11
87 Correct 2483 ms 93304 KB answer = 11
88 Correct 3089 ms 93304 KB answer = 6
89 Correct 2839 ms 93304 KB answer = 4
90 Correct 2546 ms 93304 KB answer = 2
91 Correct 1956 ms 93304 KB answer = 2
92 Correct 1636 ms 93304 KB answer = 2
93 Correct 4126 ms 93444 KB answer = 7211
94 Correct 3849 ms 93444 KB answer = 7032
95 Correct 3709 ms 93444 KB answer = 7092
96 Correct 5133 ms 93444 KB answer = 14167
97 Correct 4963 ms 93444 KB answer = 14159
98 Correct 5076 ms 93444 KB answer = 14125
99 Correct 5166 ms 93444 KB answer = 14121
100 Correct 4853 ms 93444 KB answer = 14010
101 Correct 4863 ms 93444 KB answer = 13976
102 Correct 1653 ms 93304 KB answer = 3
103 Correct 1646 ms 93304 KB answer = 2
104 Correct 2283 ms 93304 KB answer = 3
105 Correct 1693 ms 93304 KB answer = 2
106 Correct 1643 ms 93304 KB answer = 3
107 Correct 1786 ms 93304 KB answer = 4
108 Correct 1543 ms 93304 KB answer = 5
109 Correct 1269 ms 93304 KB answer = 8
110 Correct 946 ms 93304 KB answer = 22
111 Correct 4003 ms 93444 KB answer = 6760
112 Correct 3976 ms 93444 KB answer = 6788
113 Correct 3906 ms 93444 KB answer = 6632