oj.uz

Submission #42402

# Submission time Handle Problem Language Result Execution time Memory
42402 2018-02-26T17:03:24 Z Aidyn_A Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 3899 ms 136728 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <stdio.h>
#include <bits/stdc++.h>			

#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = (int)1e5 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;

int n, a[N], b[N];
int half = 10;
pii dp[(1<<10) + 123][(1<<10) + 123][11];
int now[N], pr[N];

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", &b[i]);
	int res = -1, res_p = -1;
	for(int i = 1; i <= n; i ++) {
	  now[i] = 1;
		//GET
		int j = 0, origin = (a[i] >> half), firsthalf = (a[i] >> half);
		for(int mask = 0; mask < (1 << half); mask ++) {
			int left = b[i] - __builtin_popcount(origin & mask);
			if(left >= 0 && left <= 10) {
				int lasthalf = (a[i] & ((1 << half) - 1));
				if(dp[mask][lasthalf][left].F + 1 > now[i]) {
					now[i] = dp[mask][lasthalf][left].F + 1;				
					j = dp[mask][lasthalf][left].S;  
				}
			}
		}
		pr[i] = j;
		for(int mask = 0; mask < (1 << half); mask ++) {
			int changed = __builtin_popcount(a[i] & mask);
			if(dp[firsthalf][mask][changed].F < now[i]) 
				dp[firsthalf][mask][changed] = {now[i], i};
		}
		if(now[i] > res)
			res = now[i], res_p = i;
	}
	printf("%d\n", res);
	vector<int> v;
	while(res_p > 0) {
		v.pb(res_p);
		res_p = pr[res_p];		
	}
	for(int i = sz(v) - 1; i >= 0; i --)
		printf("%d ", v[i]);
	return 0;  
}

Compilation message

subsequence.cpp: In function 'int main()':
subsequence.cpp:41:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
subsequence.cpp:43:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^
subsequence.cpp:45:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &b[i]);
                     ^

Subtask #1
7.0 / 7.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB answer = 4
2 Correct 3 ms 716 KB answer = 1
3 Correct 2 ms 788 KB answer = 2
4 Correct 1 ms 788 KB answer = 1
5 Correct 3 ms 788 KB answer = 2
6 Correct 2 ms 880 KB answer = 1
7 Correct 2 ms 880 KB answer = 1
8 Correct 8 ms 2004 KB answer = 3
9 Correct 9 ms 2004 KB answer = 2
10 Correct 9 ms 2004 KB answer = 3
11 Correct 5 ms 2004 KB answer = 2
12 Correct 8 ms 2140 KB answer = 3
13 Correct 8 ms 2140 KB answer = 2
14 Correct 13 ms 2140 KB answer = 1
15 Correct 12 ms 2140 KB answer = 1
16 Correct 15 ms 2140 KB answer = 1
17 Correct 15 ms 2140 KB answer = 1
18 Correct 7 ms 2140 KB answer = 1
19 Correct 7 ms 2140 KB answer = 1
20 Correct 6 ms 2140 KB answer = 1
21 Correct 7 ms 2140 KB answer = 1
22 Correct 222 ms 94444 KB answer = 358
23 Correct 212 ms 94572 KB answer = 336
24 Correct 214 ms 94572 KB answer = 339
25 Correct 219 ms 94648 KB answer = 357
26 Correct 209 ms 94648 KB answer = 354
27 Correct 199 ms 94648 KB answer = 333
28 Correct 203 ms 94648 KB answer = 314
29 Correct 218 ms 94648 KB answer = 322
30 Correct 205 ms 94648 KB answer = 339
31 Correct 200 ms 94648 KB answer = 351
32 Correct 252 ms 94648 KB answer = 1
33 Correct 272 ms 94648 KB answer = 1
34 Correct 260 ms 94648 KB answer = 1
35 Correct 255 ms 94648 KB answer = 1
36 Correct 256 ms 94648 KB answer = 1
37 Correct 75 ms 94648 KB answer = 1
38 Correct 70 ms 94648 KB answer = 1
39 Correct 69 ms 94648 KB answer = 1
40 Correct 70 ms 94648 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB answer = 4
2 Correct 3 ms 716 KB answer = 1
3 Correct 2 ms 788 KB answer = 2
4 Correct 1 ms 788 KB answer = 1
5 Correct 3 ms 788 KB answer = 2
6 Correct 2 ms 880 KB answer = 1
7 Correct 2 ms 880 KB answer = 1
8 Correct 8 ms 2004 KB answer = 3
9 Correct 9 ms 2004 KB answer = 2
10 Correct 9 ms 2004 KB answer = 3
11 Correct 5 ms 2004 KB answer = 2
12 Correct 8 ms 2140 KB answer = 3
13 Correct 8 ms 2140 KB answer = 2
14 Correct 13 ms 2140 KB answer = 1
15 Correct 12 ms 2140 KB answer = 1
16 Correct 15 ms 2140 KB answer = 1
17 Correct 15 ms 2140 KB answer = 1
18 Correct 7 ms 2140 KB answer = 1
19 Correct 7 ms 2140 KB answer = 1
20 Correct 6 ms 2140 KB answer = 1
21 Correct 7 ms 2140 KB answer = 1
22 Correct 222 ms 94444 KB answer = 358
23 Correct 212 ms 94572 KB answer = 336
24 Correct 214 ms 94572 KB answer = 339
25 Correct 219 ms 94648 KB answer = 357
26 Correct 209 ms 94648 KB answer = 354
27 Correct 199 ms 94648 KB answer = 333
28 Correct 203 ms 94648 KB answer = 314
29 Correct 218 ms 94648 KB answer = 322
30 Correct 205 ms 94648 KB answer = 339
31 Correct 200 ms 94648 KB answer = 351
32 Correct 252 ms 94648 KB answer = 1
33 Correct 272 ms 94648 KB answer = 1
34 Correct 260 ms 94648 KB answer = 1
35 Correct 255 ms 94648 KB answer = 1
36 Correct 256 ms 94648 KB answer = 1
37 Correct 75 ms 94648 KB answer = 1
38 Correct 70 ms 94648 KB answer = 1
39 Correct 69 ms 94648 KB answer = 1
40 Correct 70 ms 94648 KB answer = 1
41 Correct 986 ms 94648 KB answer = 6296
42 Correct 964 ms 94648 KB answer = 6267
43 Correct 976 ms 94648 KB answer = 6264
44 Correct 976 ms 94648 KB answer = 6384
45 Correct 1016 ms 94648 KB answer = 6272
46 Correct 913 ms 94648 KB answer = 6177
47 Correct 963 ms 94648 KB answer = 6144
48 Correct 917 ms 94648 KB answer = 6272
49 Correct 908 ms 94648 KB answer = 6241
50 Correct 948 ms 94648 KB answer = 6169
51 Correct 353 ms 94648 KB answer = 1
52 Correct 345 ms 94648 KB answer = 1
53 Correct 342 ms 94648 KB answer = 1
54 Correct 342 ms 94648 KB answer = 1
55 Correct 344 ms 94648 KB answer = 1
56 Correct 774 ms 94648 KB answer = 1426
57 Correct 785 ms 94648 KB answer = 1427
58 Correct 834 ms 94648 KB answer = 1428
59 Correct 780 ms 94648 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB answer = 4
2 Correct 3 ms 716 KB answer = 1
3 Correct 2 ms 788 KB answer = 2
4 Correct 1 ms 788 KB answer = 1
5 Correct 3 ms 788 KB answer = 2
6 Correct 2 ms 880 KB answer = 1
7 Correct 2 ms 880 KB answer = 1
8 Correct 8 ms 2004 KB answer = 3
9 Correct 9 ms 2004 KB answer = 2
10 Correct 9 ms 2004 KB answer = 3
11 Correct 5 ms 2004 KB answer = 2
12 Correct 8 ms 2140 KB answer = 3
13 Correct 8 ms 2140 KB answer = 2
14 Correct 13 ms 2140 KB answer = 1
15 Correct 12 ms 2140 KB answer = 1
16 Correct 15 ms 2140 KB answer = 1
17 Correct 15 ms 2140 KB answer = 1
18 Correct 7 ms 2140 KB answer = 1
19 Correct 7 ms 2140 KB answer = 1
20 Correct 6 ms 2140 KB answer = 1
21 Correct 7 ms 2140 KB answer = 1
22 Correct 222 ms 94444 KB answer = 358
23 Correct 212 ms 94572 KB answer = 336
24 Correct 214 ms 94572 KB answer = 339
25 Correct 219 ms 94648 KB answer = 357
26 Correct 209 ms 94648 KB answer = 354
27 Correct 199 ms 94648 KB answer = 333
28 Correct 203 ms 94648 KB answer = 314
29 Correct 218 ms 94648 KB answer = 322
30 Correct 205 ms 94648 KB answer = 339
31 Correct 200 ms 94648 KB answer = 351
32 Correct 252 ms 94648 KB answer = 1
33 Correct 272 ms 94648 KB answer = 1
34 Correct 260 ms 94648 KB answer = 1
35 Correct 255 ms 94648 KB answer = 1
36 Correct 256 ms 94648 KB answer = 1
37 Correct 75 ms 94648 KB answer = 1
38 Correct 70 ms 94648 KB answer = 1
39 Correct 69 ms 94648 KB answer = 1
40 Correct 70 ms 94648 KB answer = 1
41 Correct 986 ms 94648 KB answer = 6296
42 Correct 964 ms 94648 KB answer = 6267
43 Correct 976 ms 94648 KB answer = 6264
44 Correct 976 ms 94648 KB answer = 6384
45 Correct 1016 ms 94648 KB answer = 6272
46 Correct 913 ms 94648 KB answer = 6177
47 Correct 963 ms 94648 KB answer = 6144
48 Correct 917 ms 94648 KB answer = 6272
49 Correct 908 ms 94648 KB answer = 6241
50 Correct 948 ms 94648 KB answer = 6169
51 Correct 353 ms 94648 KB answer = 1
52 Correct 345 ms 94648 KB answer = 1
53 Correct 342 ms 94648 KB answer = 1
54 Correct 342 ms 94648 KB answer = 1
55 Correct 344 ms 94648 KB answer = 1
56 Correct 774 ms 94648 KB answer = 1426
57 Correct 785 ms 94648 KB answer = 1427
58 Correct 834 ms 94648 KB answer = 1428
59 Correct 780 ms 94648 KB answer = 1427
60 Correct 2851 ms 96792 KB answer = 7034
61 Correct 2798 ms 96792 KB answer = 7045
62 Correct 2959 ms 97000 KB answer = 7147
63 Correct 2798 ms 97000 KB answer = 7038
64 Correct 2827 ms 97000 KB answer = 7169
65 Correct 2891 ms 97000 KB answer = 6735
66 Correct 2865 ms 97000 KB answer = 6713
67 Correct 2804 ms 97000 KB answer = 6748
68 Correct 2736 ms 97000 KB answer = 6607
69 Correct 2743 ms 97000 KB answer = 6722
70 Correct 3865 ms 97000 KB answer = 1
71 Correct 3844 ms 97692 KB answer = 1
72 Correct 3896 ms 98884 KB answer = 1
73 Correct 3815 ms 99740 KB answer = 1
74 Correct 3899 ms 100500 KB answer = 1
75 Correct 1364 ms 100500 KB answer = 1
76 Correct 1348 ms 100500 KB answer = 1
77 Correct 1226 ms 100500 KB answer = 1
78 Correct 1234 ms 100500 KB answer = 1
79 Correct 1496 ms 100500 KB answer = 21
80 Correct 1689 ms 100500 KB answer = 7
81 Correct 1957 ms 100500 KB answer = 3
82 Correct 1863 ms 102896 KB answer = 2
83 Correct 1673 ms 102896 KB answer = 1
84 Correct 1499 ms 102896 KB answer = 1
85 Correct 1308 ms 102896 KB answer = 1
86 Correct 1498 ms 102896 KB answer = 11
87 Correct 1757 ms 102896 KB answer = 11
88 Correct 2140 ms 102896 KB answer = 6
89 Correct 2181 ms 109248 KB answer = 4
90 Correct 1814 ms 109248 KB answer = 2
91 Correct 1527 ms 109248 KB answer = 2
92 Correct 1368 ms 109248 KB answer = 2
93 Correct 2818 ms 118156 KB answer = 7211
94 Correct 2806 ms 118952 KB answer = 7032
95 Correct 2816 ms 120088 KB answer = 7092
96 Correct 3458 ms 121020 KB answer = 14167
97 Correct 3485 ms 121856 KB answer = 14159
98 Correct 3393 ms 122700 KB answer = 14125
99 Correct 3525 ms 123824 KB answer = 14121
100 Correct 3453 ms 124560 KB answer = 14010
101 Correct 3344 ms 125552 KB answer = 13976
102 Correct 1276 ms 125552 KB answer = 3
103 Correct 1465 ms 125552 KB answer = 2
104 Correct 1738 ms 125552 KB answer = 3
105 Correct 1262 ms 125552 KB answer = 2
106 Correct 1228 ms 125552 KB answer = 3
107 Correct 1318 ms 125868 KB answer = 4
108 Correct 1250 ms 125868 KB answer = 5
109 Correct 921 ms 125868 KB answer = 8
110 Correct 710 ms 125868 KB answer = 22
111 Correct 2853 ms 135164 KB answer = 6760
112 Correct 2907 ms 135572 KB answer = 6788
113 Correct 2839 ms 136728 KB answer = 6632