oj.uz

답안 #36128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36128 2017-12-06T02:46:15 Z aome Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 5099 ms 48776 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int M = 1024;
const int INF = 1e9;

int n, a[N], b[N], cnt[M];
int f[N], trace[N];
int g[M][M][11];

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < 10; ++j) cnt[i] += i >> j & 1;
	}
	int pos = 0; f[0] = -INF;
	for (int i = 1; i <= n; ++i) {
		int pre = 0, suf = 0;
		for (int j = 0; j < 10; ++j) {
			if (a[i] >> j & 1) pre |= 1 << j;
		}
		for (int j = 10; j < 20; ++j) {
			if (a[i] >> j & 1) suf |= 1 << (j - 10);
		}
		f[i] = 1;
		for (int j = 0; j < M; ++j) {
			int x = j & pre;
			if (cnt[x] > b[i] || b[i] - cnt[x] > 10) continue;
			int y = g[j][suf][b[i] - cnt[x]];
			if (f[i] < f[y] + 1) {
				f[i] = f[y] + 1, trace[i] = y;
			}
		}
		for (int j = 0; j < M; ++j) {
			int x = suf & j;
			int &y = g[pre][j][cnt[x]];
			if (f[y] < f[i]) y = i;
		}
		if (f[pos] < f[i]) pos = i;
	}
	vector<int> res;
	int cur = pos;
	while (cur) {
		res.push_back(cur), cur = trace[cur];
	}
	reverse(res.begin(), res.end());
	printf("%d\n", res.size());
	for (int i = 0; i < res.size(); ++i) printf("%d ", res[i]);
}

Compilation message

subsequence.cpp: In function 'int main()':
subsequence.cpp:52:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", res.size());
                           ^
subsequence.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < res.size(); ++i) printf("%d ", res[i]);
                    ^
subsequence.cpp:15:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
subsequence.cpp:16:49: 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:17:49: 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", &b[i]);
                                                 ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 48636 KB answer = 4
2 Correct 0 ms 48636 KB answer = 1
3 Correct 0 ms 48636 KB answer = 2
4 Correct 0 ms 48636 KB answer = 1
5 Correct 0 ms 48636 KB answer = 2
6 Correct 0 ms 48636 KB answer = 1
7 Correct 0 ms 48636 KB answer = 1
8 Correct 0 ms 48636 KB answer = 3
9 Correct 3 ms 48636 KB answer = 2
10 Correct 3 ms 48636 KB answer = 3
11 Correct 0 ms 48636 KB answer = 2
12 Correct 0 ms 48636 KB answer = 3
13 Correct 3 ms 48636 KB answer = 2
14 Correct 0 ms 48636 KB answer = 1
15 Correct 3 ms 48636 KB answer = 1
16 Correct 0 ms 48636 KB answer = 1
17 Correct 0 ms 48636 KB answer = 1
18 Correct 0 ms 48636 KB answer = 1
19 Correct 0 ms 48636 KB answer = 1
20 Correct 0 ms 48636 KB answer = 1
21 Correct 0 ms 48636 KB answer = 1

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 48636 KB answer = 4
2 Correct 0 ms 48636 KB answer = 1
3 Correct 0 ms 48636 KB answer = 2
4 Correct 0 ms 48636 KB answer = 1
5 Correct 0 ms 48636 KB answer = 2
6 Correct 0 ms 48636 KB answer = 1
7 Correct 0 ms 48636 KB answer = 1
8 Correct 0 ms 48636 KB answer = 3
9 Correct 3 ms 48636 KB answer = 2
10 Correct 3 ms 48636 KB answer = 3
11 Correct 0 ms 48636 KB answer = 2
12 Correct 0 ms 48636 KB answer = 3
13 Correct 3 ms 48636 KB answer = 2
14 Correct 0 ms 48636 KB answer = 1
15 Correct 3 ms 48636 KB answer = 1
16 Correct 0 ms 48636 KB answer = 1
17 Correct 0 ms 48636 KB answer = 1
18 Correct 0 ms 48636 KB answer = 1
19 Correct 0 ms 48636 KB answer = 1
20 Correct 0 ms 48636 KB answer = 1
21 Correct 0 ms 48636 KB answer = 1
22 Correct 126 ms 48636 KB answer = 358
23 Correct 136 ms 48636 KB answer = 336
24 Correct 123 ms 48636 KB answer = 339
25 Correct 146 ms 48636 KB answer = 357
26 Correct 139 ms 48636 KB answer = 354
27 Correct 113 ms 48636 KB answer = 333
28 Correct 143 ms 48636 KB answer = 314
29 Correct 139 ms 48636 KB answer = 322
30 Correct 116 ms 48636 KB answer = 339
31 Correct 129 ms 48636 KB answer = 351
32 Correct 186 ms 48636 KB answer = 1
33 Correct 203 ms 48636 KB answer = 1
34 Correct 166 ms 48636 KB answer = 1
35 Correct 183 ms 48636 KB answer = 1
36 Correct 199 ms 48636 KB answer = 1
37 Correct 89 ms 48636 KB answer = 1
38 Correct 59 ms 48636 KB answer = 1
39 Correct 56 ms 48636 KB answer = 1
40 Correct 69 ms 48636 KB answer = 1

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 48636 KB answer = 4
2 Correct 0 ms 48636 KB answer = 1
3 Correct 0 ms 48636 KB answer = 2
4 Correct 0 ms 48636 KB answer = 1
5 Correct 0 ms 48636 KB answer = 2
6 Correct 0 ms 48636 KB answer = 1
7 Correct 0 ms 48636 KB answer = 1
8 Correct 0 ms 48636 KB answer = 3
9 Correct 3 ms 48636 KB answer = 2
10 Correct 3 ms 48636 KB answer = 3
11 Correct 0 ms 48636 KB answer = 2
12 Correct 0 ms 48636 KB answer = 3
13 Correct 3 ms 48636 KB answer = 2
14 Correct 0 ms 48636 KB answer = 1
15 Correct 3 ms 48636 KB answer = 1
16 Correct 0 ms 48636 KB answer = 1
17 Correct 0 ms 48636 KB answer = 1
18 Correct 0 ms 48636 KB answer = 1
19 Correct 0 ms 48636 KB answer = 1
20 Correct 0 ms 48636 KB answer = 1
21 Correct 0 ms 48636 KB answer = 1
22 Correct 126 ms 48636 KB answer = 358
23 Correct 136 ms 48636 KB answer = 336
24 Correct 123 ms 48636 KB answer = 339
25 Correct 146 ms 48636 KB answer = 357
26 Correct 139 ms 48636 KB answer = 354
27 Correct 113 ms 48636 KB answer = 333
28 Correct 143 ms 48636 KB answer = 314
29 Correct 139 ms 48636 KB answer = 322
30 Correct 116 ms 48636 KB answer = 339
31 Correct 129 ms 48636 KB answer = 351
32 Correct 186 ms 48636 KB answer = 1
33 Correct 203 ms 48636 KB answer = 1
34 Correct 166 ms 48636 KB answer = 1
35 Correct 183 ms 48636 KB answer = 1
36 Correct 199 ms 48636 KB answer = 1
37 Correct 89 ms 48636 KB answer = 1
38 Correct 59 ms 48636 KB answer = 1
39 Correct 56 ms 48636 KB answer = 1
40 Correct 69 ms 48636 KB answer = 1
41 Correct 739 ms 48776 KB answer = 6296
42 Correct 783 ms 48776 KB answer = 6267
43 Correct 939 ms 48776 KB answer = 6264
44 Correct 873 ms 48776 KB answer = 6384
45 Correct 1039 ms 48776 KB answer = 6272
46 Correct 823 ms 48776 KB answer = 6177
47 Correct 696 ms 48776 KB answer = 6144
48 Correct 699 ms 48776 KB answer = 6272
49 Correct 829 ms 48776 KB answer = 6241
50 Correct 713 ms 48776 KB answer = 6169
51 Correct 429 ms 48636 KB answer = 1
52 Correct 426 ms 48636 KB answer = 1
53 Correct 473 ms 48636 KB answer = 1
54 Correct 446 ms 48636 KB answer = 1
55 Correct 476 ms 48636 KB answer = 1
56 Correct 849 ms 48636 KB answer = 1426
57 Correct 856 ms 48636 KB answer = 1427
58 Correct 869 ms 48636 KB answer = 1428
59 Correct 883 ms 48636 KB answer = 1427

Subtask #4
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 48636 KB answer = 4
2 Correct 0 ms 48636 KB answer = 1
3 Correct 0 ms 48636 KB answer = 2
4 Correct 0 ms 48636 KB answer = 1
5 Correct 0 ms 48636 KB answer = 2
6 Correct 0 ms 48636 KB answer = 1
7 Correct 0 ms 48636 KB answer = 1
8 Correct 0 ms 48636 KB answer = 3
9 Correct 3 ms 48636 KB answer = 2
10 Correct 3 ms 48636 KB answer = 3
11 Correct 0 ms 48636 KB answer = 2
12 Correct 0 ms 48636 KB answer = 3
13 Correct 3 ms 48636 KB answer = 2
14 Correct 0 ms 48636 KB answer = 1
15 Correct 3 ms 48636 KB answer = 1
16 Correct 0 ms 48636 KB answer = 1
17 Correct 0 ms 48636 KB answer = 1
18 Correct 0 ms 48636 KB answer = 1
19 Correct 0 ms 48636 KB answer = 1
20 Correct 0 ms 48636 KB answer = 1
21 Correct 0 ms 48636 KB answer = 1
22 Correct 126 ms 48636 KB answer = 358
23 Correct 136 ms 48636 KB answer = 336
24 Correct 123 ms 48636 KB answer = 339
25 Correct 146 ms 48636 KB answer = 357
26 Correct 139 ms 48636 KB answer = 354
27 Correct 113 ms 48636 KB answer = 333
28 Correct 143 ms 48636 KB answer = 314
29 Correct 139 ms 48636 KB answer = 322
30 Correct 116 ms 48636 KB answer = 339
31 Correct 129 ms 48636 KB answer = 351
32 Correct 186 ms 48636 KB answer = 1
33 Correct 203 ms 48636 KB answer = 1
34 Correct 166 ms 48636 KB answer = 1
35 Correct 183 ms 48636 KB answer = 1
36 Correct 199 ms 48636 KB answer = 1
37 Correct 89 ms 48636 KB answer = 1
38 Correct 59 ms 48636 KB answer = 1
39 Correct 56 ms 48636 KB answer = 1
40 Correct 69 ms 48636 KB answer = 1
41 Correct 739 ms 48776 KB answer = 6296
42 Correct 783 ms 48776 KB answer = 6267
43 Correct 939 ms 48776 KB answer = 6264
44 Correct 873 ms 48776 KB answer = 6384
45 Correct 1039 ms 48776 KB answer = 6272
46 Correct 823 ms 48776 KB answer = 6177
47 Correct 696 ms 48776 KB answer = 6144
48 Correct 699 ms 48776 KB answer = 6272
49 Correct 829 ms 48776 KB answer = 6241
50 Correct 713 ms 48776 KB answer = 6169
51 Correct 429 ms 48636 KB answer = 1
52 Correct 426 ms 48636 KB answer = 1
53 Correct 473 ms 48636 KB answer = 1
54 Correct 446 ms 48636 KB answer = 1
55 Correct 476 ms 48636 KB answer = 1
56 Correct 849 ms 48636 KB answer = 1426
57 Correct 856 ms 48636 KB answer = 1427
58 Correct 869 ms 48636 KB answer = 1428
59 Correct 883 ms 48636 KB answer = 1427
60 Correct 3296 ms 48776 KB answer = 7034
61 Correct 3403 ms 48776 KB answer = 7045
62 Correct 3366 ms 48776 KB answer = 7147
63 Correct 3159 ms 48776 KB answer = 7038
64 Correct 3316 ms 48776 KB answer = 7169
65 Correct 3343 ms 48776 KB answer = 6735
66 Correct 3433 ms 48776 KB answer = 6713
67 Correct 3323 ms 48776 KB answer = 6748
68 Correct 3546 ms 48776 KB answer = 6607
69 Correct 3463 ms 48776 KB answer = 6722
70 Correct 4846 ms 48636 KB answer = 1
71 Correct 4869 ms 48636 KB answer = 1
72 Correct 4779 ms 48636 KB answer = 1
73 Correct 5099 ms 48636 KB answer = 1
74 Correct 4939 ms 48636 KB answer = 1
75 Correct 1929 ms 48636 KB answer = 1
76 Correct 1916 ms 48636 KB answer = 1
77 Correct 1889 ms 48636 KB answer = 1
78 Correct 2003 ms 48636 KB answer = 1
79 Correct 1206 ms 48636 KB answer = 21
80 Correct 1336 ms 48636 KB answer = 7
81 Correct 1526 ms 48636 KB answer = 3
82 Correct 1606 ms 48636 KB answer = 2
83 Correct 1619 ms 48636 KB answer = 1
84 Correct 1689 ms 48636 KB answer = 1
85 Correct 1819 ms 48636 KB answer = 1
86 Correct 1296 ms 48636 KB answer = 11
87 Correct 1403 ms 48636 KB answer = 11
88 Correct 1573 ms 48636 KB answer = 6
89 Correct 1603 ms 48636 KB answer = 4
90 Correct 1789 ms 48636 KB answer = 2
91 Correct 1743 ms 48636 KB answer = 2
92 Correct 1699 ms 48636 KB answer = 2
93 Correct 3129 ms 48776 KB answer = 7211
94 Correct 3233 ms 48776 KB answer = 7032
95 Correct 3116 ms 48776 KB answer = 7092
96 Correct 4273 ms 48776 KB answer = 14167
97 Correct 4173 ms 48776 KB answer = 14159
98 Correct 4183 ms 48776 KB answer = 14125
99 Correct 4513 ms 48776 KB answer = 14121
100 Correct 4062 ms 48776 KB answer = 14010
101 Correct 3996 ms 48776 KB answer = 13976
102 Correct 1769 ms 48636 KB answer = 3
103 Correct 1773 ms 48636 KB answer = 2
104 Correct 1609 ms 48636 KB answer = 3
105 Correct 1783 ms 48636 KB answer = 2
106 Correct 1719 ms 48636 KB answer = 3
107 Correct 1703 ms 48636 KB answer = 4
108 Correct 1513 ms 48636 KB answer = 5
109 Correct 1176 ms 48636 KB answer = 8
110 Correct 846 ms 48636 KB answer = 22
111 Correct 3313 ms 48776 KB answer = 6760
112 Correct 3236 ms 48776 KB answer = 6788
113 Correct 3073 ms 48776 KB answer = 6632