oj.uz

답안 #386253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386253 2021-04-06T08:28:19 Z patrikpavic2 Longest beautiful sequence (IZhO17_subsequence) C++17
100 / 100
 2692 ms 98524 KB 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>

#define PB push_back

using namespace std;

const int N = 1e5 + 500;
const int MSK = (1 << 20);
const int BS = (1 << 10);

int n, A[N], K[N], dp[N], rek[N], krj;
int naj[MSK][11], sol, naj2[MSK][11];
vector < int > na[BS][11];

void dodaj(int xx, int y, int gdje){	
	int i = xx >> 10, x = xx & (BS - 1);
	for(int j = 0;j < BS;j++){
		int ds = __builtin_popcount(j & x);
		if(y > naj[(i << 10) + j][ds]){
			naj[(i << 10) + j][ds] = y;
			naj2[(i << 10) + j][ds] = gdje;
		}
	}
}

int GDJE;

int pitaj(int x, int k){
	int ret = 0, i = x >> 10;
	for(int kk = 0;kk < 11;kk++){
		if(k - kk < 0 || k - kk > 10) continue;
		for(int j : na[i][kk]){
			if(naj[(j << 10) + (x & (BS - 1))][k - kk] > ret){
				ret = naj[(j << 10) + (x & (BS - 1))][k - kk];
				GDJE = naj2[(j << 10) + (x & (BS - 1))][k - kk];
			}
		}
	}
	return ret;
}

int main(){
	for(int i = 0;i < BS;i++)
		for(int j = 0;j < BS;j++)
			na[i][__builtin_popcount(i & j)].PB(j);
	scanf("%d", &n);
	for(int i = 0;i < n;i++)
		scanf("%d", A + i);
	for(int i = 0;i < n;i++)
		scanf("%d", K + i);
	for(int i = 0;i < n;i++){
		dp[i] = pitaj(A[i], K[i]) + 1;
		if(dp[i] > 1){
			rek[i] = GDJE;
		}
		if(sol < dp[i]){
			sol = dp[i];
			krj = i;
		}
		dodaj(A[i], dp[i], i);
	}
	printf("%d\n", sol);
	vector < int > fin;
	for(;;){
		fin.PB(krj + 1);
		if(dp[krj] == 1) break;
		krj = rek[krj];
	}
	reverse(fin.begin(), fin.end());
	for(int x : fin)
		printf("%d ", x);
	printf("\n");
	return 0;
}

Compilation message

subsequence.cpp: In function 'int main()':
subsequence.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
subsequence.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   scanf("%d", K + i);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 6380 KB answer = 4
2 Correct 13 ms 6380 KB answer = 1
3 Correct 15 ms 6380 KB answer = 2
4 Correct 12 ms 6252 KB answer = 1
5 Correct 16 ms 6380 KB answer = 2
6 Correct 12 ms 6636 KB answer = 1
7 Correct 12 ms 6380 KB answer = 1
8 Correct 15 ms 7660 KB answer = 3
9 Correct 17 ms 7592 KB answer = 2
10 Correct 17 ms 7532 KB answer = 3
11 Correct 15 ms 7532 KB answer = 2
12 Correct 16 ms 7788 KB answer = 3
13 Correct 15 ms 7532 KB answer = 2
14 Correct 19 ms 7404 KB answer = 1
15 Correct 18 ms 7788 KB answer = 1
16 Correct 18 ms 7788 KB answer = 1
17 Correct 18 ms 7532 KB answer = 1
18 Correct 15 ms 6508 KB answer = 1
19 Correct 15 ms 6508 KB answer = 1
20 Correct 15 ms 6528 KB answer = 1
21 Correct 15 ms 6508 KB answer = 1

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 6380 KB answer = 4
2 Correct 13 ms 6380 KB answer = 1
3 Correct 15 ms 6380 KB answer = 2
4 Correct 12 ms 6252 KB answer = 1
5 Correct 16 ms 6380 KB answer = 2
6 Correct 12 ms 6636 KB answer = 1
7 Correct 12 ms 6380 KB answer = 1
8 Correct 15 ms 7660 KB answer = 3
9 Correct 17 ms 7592 KB answer = 2
10 Correct 17 ms 7532 KB answer = 3
11 Correct 15 ms 7532 KB answer = 2
12 Correct 16 ms 7788 KB answer = 3
13 Correct 15 ms 7532 KB answer = 2
14 Correct 19 ms 7404 KB answer = 1
15 Correct 18 ms 7788 KB answer = 1
16 Correct 18 ms 7788 KB answer = 1
17 Correct 18 ms 7532 KB answer = 1
18 Correct 15 ms 6508 KB answer = 1
19 Correct 15 ms 6508 KB answer = 1
20 Correct 15 ms 6528 KB answer = 1
21 Correct 15 ms 6508 KB answer = 1
22 Correct 160 ms 96108 KB answer = 358
23 Correct 158 ms 96108 KB answer = 336
24 Correct 164 ms 95852 KB answer = 339
25 Correct 162 ms 96236 KB answer = 357
26 Correct 170 ms 96108 KB answer = 354
27 Correct 153 ms 90092 KB answer = 333
28 Correct 151 ms 91272 KB answer = 314
29 Correct 155 ms 90604 KB answer = 322
30 Correct 157 ms 91500 KB answer = 339
31 Correct 155 ms 90348 KB answer = 351
32 Correct 195 ms 92012 KB answer = 1
33 Correct 202 ms 92012 KB answer = 1
34 Correct 190 ms 91628 KB answer = 1
35 Correct 198 ms 92012 KB answer = 1
36 Correct 195 ms 91244 KB answer = 1
37 Correct 67 ms 10604 KB answer = 1
38 Correct 67 ms 10604 KB answer = 1
39 Correct 66 ms 10604 KB answer = 1
40 Correct 67 ms 10604 KB answer = 1

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 6380 KB answer = 4
2 Correct 13 ms 6380 KB answer = 1
3 Correct 15 ms 6380 KB answer = 2
4 Correct 12 ms 6252 KB answer = 1
5 Correct 16 ms 6380 KB answer = 2
6 Correct 12 ms 6636 KB answer = 1
7 Correct 12 ms 6380 KB answer = 1
8 Correct 15 ms 7660 KB answer = 3
9 Correct 17 ms 7592 KB answer = 2
10 Correct 17 ms 7532 KB answer = 3
11 Correct 15 ms 7532 KB answer = 2
12 Correct 16 ms 7788 KB answer = 3
13 Correct 15 ms 7532 KB answer = 2
14 Correct 19 ms 7404 KB answer = 1
15 Correct 18 ms 7788 KB answer = 1
16 Correct 18 ms 7788 KB answer = 1
17 Correct 18 ms 7532 KB answer = 1
18 Correct 15 ms 6508 KB answer = 1
19 Correct 15 ms 6508 KB answer = 1
20 Correct 15 ms 6528 KB answer = 1
21 Correct 15 ms 6508 KB answer = 1
22 Correct 160 ms 96108 KB answer = 358
23 Correct 158 ms 96108 KB answer = 336
24 Correct 164 ms 95852 KB answer = 339
25 Correct 162 ms 96236 KB answer = 357
26 Correct 170 ms 96108 KB answer = 354
27 Correct 153 ms 90092 KB answer = 333
28 Correct 151 ms 91272 KB answer = 314
29 Correct 155 ms 90604 KB answer = 322
30 Correct 157 ms 91500 KB answer = 339
31 Correct 155 ms 90348 KB answer = 351
32 Correct 195 ms 92012 KB answer = 1
33 Correct 202 ms 92012 KB answer = 1
34 Correct 190 ms 91628 KB answer = 1
35 Correct 198 ms 92012 KB answer = 1
36 Correct 195 ms 91244 KB answer = 1
37 Correct 67 ms 10604 KB answer = 1
38 Correct 67 ms 10604 KB answer = 1
39 Correct 66 ms 10604 KB answer = 1
40 Correct 67 ms 10604 KB answer = 1
41 Correct 886 ms 8044 KB answer = 6296
42 Correct 878 ms 8028 KB answer = 6267
43 Correct 897 ms 8044 KB answer = 6264
44 Correct 981 ms 8032 KB answer = 6384
45 Correct 892 ms 8252 KB answer = 6272
46 Correct 901 ms 8068 KB answer = 6177
47 Correct 899 ms 8084 KB answer = 6144
48 Correct 926 ms 8076 KB answer = 6272
49 Correct 940 ms 8012 KB answer = 6241
50 Correct 900 ms 8092 KB answer = 6169
51 Correct 495 ms 7544 KB answer = 1
52 Correct 485 ms 7532 KB answer = 1
53 Correct 493 ms 7608 KB answer = 1
54 Correct 506 ms 7528 KB answer = 1
55 Correct 521 ms 7604 KB answer = 1
56 Correct 972 ms 8016 KB answer = 1426
57 Correct 977 ms 8020 KB answer = 1427
58 Correct 961 ms 8020 KB answer = 1428
59 Correct 960 ms 7916 KB answer = 1427

Subtask #4
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 6380 KB answer = 4
2 Correct 13 ms 6380 KB answer = 1
3 Correct 15 ms 6380 KB answer = 2
4 Correct 12 ms 6252 KB answer = 1
5 Correct 16 ms 6380 KB answer = 2
6 Correct 12 ms 6636 KB answer = 1
7 Correct 12 ms 6380 KB answer = 1
8 Correct 15 ms 7660 KB answer = 3
9 Correct 17 ms 7592 KB answer = 2
10 Correct 17 ms 7532 KB answer = 3
11 Correct 15 ms 7532 KB answer = 2
12 Correct 16 ms 7788 KB answer = 3
13 Correct 15 ms 7532 KB answer = 2
14 Correct 19 ms 7404 KB answer = 1
15 Correct 18 ms 7788 KB answer = 1
16 Correct 18 ms 7788 KB answer = 1
17 Correct 18 ms 7532 KB answer = 1
18 Correct 15 ms 6508 KB answer = 1
19 Correct 15 ms 6508 KB answer = 1
20 Correct 15 ms 6528 KB answer = 1
21 Correct 15 ms 6508 KB answer = 1
22 Correct 160 ms 96108 KB answer = 358
23 Correct 158 ms 96108 KB answer = 336
24 Correct 164 ms 95852 KB answer = 339
25 Correct 162 ms 96236 KB answer = 357
26 Correct 170 ms 96108 KB answer = 354
27 Correct 153 ms 90092 KB answer = 333
28 Correct 151 ms 91272 KB answer = 314
29 Correct 155 ms 90604 KB answer = 322
30 Correct 157 ms 91500 KB answer = 339
31 Correct 155 ms 90348 KB answer = 351
32 Correct 195 ms 92012 KB answer = 1
33 Correct 202 ms 92012 KB answer = 1
34 Correct 190 ms 91628 KB answer = 1
35 Correct 198 ms 92012 KB answer = 1
36 Correct 195 ms 91244 KB answer = 1
37 Correct 67 ms 10604 KB answer = 1
38 Correct 67 ms 10604 KB answer = 1
39 Correct 66 ms 10604 KB answer = 1
40 Correct 67 ms 10604 KB answer = 1
41 Correct 886 ms 8044 KB answer = 6296
42 Correct 878 ms 8028 KB answer = 6267
43 Correct 897 ms 8044 KB answer = 6264
44 Correct 981 ms 8032 KB answer = 6384
45 Correct 892 ms 8252 KB answer = 6272
46 Correct 901 ms 8068 KB answer = 6177
47 Correct 899 ms 8084 KB answer = 6144
48 Correct 926 ms 8076 KB answer = 6272
49 Correct 940 ms 8012 KB answer = 6241
50 Correct 900 ms 8092 KB answer = 6169
51 Correct 495 ms 7544 KB answer = 1
52 Correct 485 ms 7532 KB answer = 1
53 Correct 493 ms 7608 KB answer = 1
54 Correct 506 ms 7528 KB answer = 1
55 Correct 521 ms 7604 KB answer = 1
56 Correct 972 ms 8016 KB answer = 1426
57 Correct 977 ms 8020 KB answer = 1427
58 Correct 961 ms 8020 KB answer = 1428
59 Correct 960 ms 7916 KB answer = 1427
60 Correct 1928 ms 98168 KB answer = 7034
61 Correct 2025 ms 98128 KB answer = 7045
62 Correct 2021 ms 98400 KB answer = 7147
63 Correct 1957 ms 98184 KB answer = 7038
64 Correct 2015 ms 98200 KB answer = 7169
65 Correct 1970 ms 98080 KB answer = 6735
66 Correct 1985 ms 98068 KB answer = 6713
67 Correct 1975 ms 97840 KB answer = 6748
68 Correct 1933 ms 97828 KB answer = 6607
69 Correct 1963 ms 98048 KB answer = 6722
70 Correct 2638 ms 97716 KB answer = 1
71 Correct 2653 ms 97592 KB answer = 1
72 Correct 2611 ms 97544 KB answer = 1
73 Correct 2632 ms 97516 KB answer = 1
74 Correct 2692 ms 97544 KB answer = 1
75 Correct 1265 ms 56884 KB answer = 1
76 Correct 1258 ms 56756 KB answer = 1
77 Correct 1248 ms 56648 KB answer = 1
78 Correct 1257 ms 56956 KB answer = 1
79 Correct 1369 ms 43048 KB answer = 21
80 Correct 1647 ms 65132 KB answer = 7
81 Correct 1753 ms 83092 KB answer = 3
82 Correct 1697 ms 93244 KB answer = 2
83 Correct 1486 ms 85004 KB answer = 1
84 Correct 1337 ms 66576 KB answer = 1
85 Correct 1235 ms 56812 KB answer = 1
86 Correct 1313 ms 42728 KB answer = 11
87 Correct 1622 ms 64964 KB answer = 11
88 Correct 1759 ms 83128 KB answer = 6
89 Correct 1700 ms 93256 KB answer = 4
90 Correct 1501 ms 85100 KB answer = 2
91 Correct 1320 ms 66756 KB answer = 2
92 Correct 1206 ms 56888 KB answer = 2
93 Correct 1893 ms 98088 KB answer = 7211
94 Correct 1883 ms 98200 KB answer = 7032
95 Correct 1882 ms 98172 KB answer = 7092
96 Correct 2558 ms 98328 KB answer = 14167
97 Correct 2548 ms 98464 KB answer = 14159
98 Correct 2561 ms 98272 KB answer = 14125
99 Correct 2596 ms 98408 KB answer = 14121
100 Correct 2541 ms 98524 KB answer = 14010
101 Correct 2554 ms 98256 KB answer = 13976
102 Correct 1247 ms 56744 KB answer = 3
103 Correct 1324 ms 66732 KB answer = 2
104 Correct 1470 ms 84972 KB answer = 3
105 Correct 1228 ms 56096 KB answer = 2
106 Correct 1182 ms 66540 KB answer = 3
107 Correct 1200 ms 93292 KB answer = 4
108 Correct 1075 ms 83180 KB answer = 5
109 Correct 887 ms 65132 KB answer = 8
110 Correct 719 ms 42948 KB answer = 22
111 Correct 1881 ms 98196 KB answer = 6760
112 Correct 1893 ms 98028 KB answer = 6788
113 Correct 1885 ms 98028 KB answer = 6632