oj.uz

Submission #964967

# Submission time Handle Problem Language Result Execution time Memory
964967 2024-04-17T19:41:42 Z AlphaMale06 Longest beautiful sequence (IZhO17_subsequence) C++17
40 / 100
 6000 ms 15792 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5+3;
const int bits=21;
int dp[1<<bits], prv[N], from[1<<bits], a[N], b[N];

int main()
{
    int n;
    cin >> n;
    for(int i=1; i<= n; i++)cin >> a[i];
    for(int i=1; i<= n; i++)cin >> b[i];
    set<int> st;
    vector<int> occ;
    for(int i=1; i<=n; i++){
        int val=1;
        int mxind=0;
        for(int j : occ){
            if(__builtin_popcount(j&a[i])==b[i]){
                if(dp[j]+1>val){
                    val=dp[j]+1;
                    mxind=from[j];
                }
            }
        }
        if(val>dp[a[i]]){
            from[a[i]]=i;
            dp[a[i]]=val;
            prv[i]=mxind;
        }
        if(st.find(a[i])==st.end()){
            st.insert(a[i]);
            occ.push_back(a[i]);
        }
    }
    int ans=0, cur=0;
    for(int i : occ){
        if(dp[i]>ans){
            ans=dp[i];
            cur=from[i];
        }
    }
    cout << ans << '\n';
    vector<int> cons;
    while(cur!=0){
        cons.push_back(cur);
        cur=prv[cur];
    }
    reverse(cons.begin(), cons.end());
    for(int e : cons)cout << e << " ";
    cout << '\n';
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB answer = 4
2 Correct 1 ms 2396 KB answer = 1
3 Correct 1 ms 2396 KB answer = 2
4 Correct 1 ms 2396 KB answer = 1
5 Correct 1 ms 2396 KB answer = 2
6 Correct 1 ms 6492 KB answer = 1
7 Correct 1 ms 6492 KB answer = 1
8 Correct 1 ms 4444 KB answer = 3
9 Correct 2 ms 8536 KB answer = 2
10 Correct 1 ms 8540 KB answer = 3
11 Correct 1 ms 6492 KB answer = 2
12 Correct 1 ms 6488 KB answer = 3
13 Correct 1 ms 8636 KB answer = 2
14 Correct 2 ms 8640 KB answer = 1
15 Correct 1 ms 6488 KB answer = 1
16 Correct 1 ms 6592 KB answer = 1
17 Correct 1 ms 6492 KB answer = 1
18 Correct 1 ms 6488 KB answer = 1
19 Correct 1 ms 6492 KB answer = 1
20 Correct 1 ms 6492 KB answer = 1
21 Correct 1 ms 6492 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB answer = 4
2 Correct 1 ms 2396 KB answer = 1
3 Correct 1 ms 2396 KB answer = 2
4 Correct 1 ms 2396 KB answer = 1
5 Correct 1 ms 2396 KB answer = 2
6 Correct 1 ms 6492 KB answer = 1
7 Correct 1 ms 6492 KB answer = 1
8 Correct 1 ms 4444 KB answer = 3
9 Correct 2 ms 8536 KB answer = 2
10 Correct 1 ms 8540 KB answer = 3
11 Correct 1 ms 6492 KB answer = 2
12 Correct 1 ms 6488 KB answer = 3
13 Correct 1 ms 8636 KB answer = 2
14 Correct 2 ms 8640 KB answer = 1
15 Correct 1 ms 6488 KB answer = 1
16 Correct 1 ms 6592 KB answer = 1
17 Correct 1 ms 6492 KB answer = 1
18 Correct 1 ms 6488 KB answer = 1
19 Correct 1 ms 6492 KB answer = 1
20 Correct 1 ms 6492 KB answer = 1
21 Correct 1 ms 6492 KB answer = 1
22 Correct 46 ms 11016 KB answer = 358
23 Correct 49 ms 11976 KB answer = 336
24 Correct 46 ms 11804 KB answer = 339
25 Correct 53 ms 11016 KB answer = 357
26 Correct 45 ms 11860 KB answer = 354
27 Correct 40 ms 11860 KB answer = 333
28 Correct 43 ms 11860 KB answer = 314
29 Correct 42 ms 11820 KB answer = 322
30 Correct 44 ms 11860 KB answer = 339
31 Correct 48 ms 11860 KB answer = 351
32 Correct 34 ms 11828 KB answer = 1
33 Correct 39 ms 11612 KB answer = 1
34 Correct 33 ms 11624 KB answer = 1
35 Correct 40 ms 11784 KB answer = 1
36 Correct 44 ms 11728 KB answer = 1
37 Correct 39 ms 6888 KB answer = 1
38 Correct 33 ms 7088 KB answer = 1
39 Correct 33 ms 7000 KB answer = 1
40 Correct 33 ms 7096 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB answer = 4
2 Correct 1 ms 2396 KB answer = 1
3 Correct 1 ms 2396 KB answer = 2
4 Correct 1 ms 2396 KB answer = 1
5 Correct 1 ms 2396 KB answer = 2
6 Correct 1 ms 6492 KB answer = 1
7 Correct 1 ms 6492 KB answer = 1
8 Correct 1 ms 4444 KB answer = 3
9 Correct 2 ms 8536 KB answer = 2
10 Correct 1 ms 8540 KB answer = 3
11 Correct 1 ms 6492 KB answer = 2
12 Correct 1 ms 6488 KB answer = 3
13 Correct 1 ms 8636 KB answer = 2
14 Correct 2 ms 8640 KB answer = 1
15 Correct 1 ms 6488 KB answer = 1
16 Correct 1 ms 6592 KB answer = 1
17 Correct 1 ms 6492 KB answer = 1
18 Correct 1 ms 6488 KB answer = 1
19 Correct 1 ms 6492 KB answer = 1
20 Correct 1 ms 6492 KB answer = 1
21 Correct 1 ms 6492 KB answer = 1
22 Correct 46 ms 11016 KB answer = 358
23 Correct 49 ms 11976 KB answer = 336
24 Correct 46 ms 11804 KB answer = 339
25 Correct 53 ms 11016 KB answer = 357
26 Correct 45 ms 11860 KB answer = 354
27 Correct 40 ms 11860 KB answer = 333
28 Correct 43 ms 11860 KB answer = 314
29 Correct 42 ms 11820 KB answer = 322
30 Correct 44 ms 11860 KB answer = 339
31 Correct 48 ms 11860 KB answer = 351
32 Correct 34 ms 11828 KB answer = 1
33 Correct 39 ms 11612 KB answer = 1
34 Correct 33 ms 11624 KB answer = 1
35 Correct 40 ms 11784 KB answer = 1
36 Correct 44 ms 11728 KB answer = 1
37 Correct 39 ms 6888 KB answer = 1
38 Correct 33 ms 7088 KB answer = 1
39 Correct 33 ms 7000 KB answer = 1
40 Correct 33 ms 7096 KB answer = 1
41 Correct 110 ms 3668 KB answer = 6296
42 Correct 123 ms 3620 KB answer = 6267
43 Correct 123 ms 3712 KB answer = 6264
44 Correct 117 ms 3664 KB answer = 6384
45 Correct 115 ms 3584 KB answer = 6272
46 Correct 78 ms 3664 KB answer = 6177
47 Correct 78 ms 3528 KB answer = 6144
48 Correct 84 ms 3752 KB answer = 6272
49 Correct 78 ms 3672 KB answer = 6241
50 Correct 82 ms 3564 KB answer = 6169
51 Correct 57 ms 3360 KB answer = 1
52 Correct 51 ms 3304 KB answer = 1
53 Correct 50 ms 3312 KB answer = 1
54 Correct 51 ms 3236 KB answer = 1
55 Correct 47 ms 3148 KB answer = 1
56 Correct 51 ms 3408 KB answer = 1426
57 Correct 46 ms 3436 KB answer = 1427
58 Correct 46 ms 3584 KB answer = 1428
59 Correct 46 ms 3464 KB answer = 1427

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB answer = 4
2 Correct 1 ms 2396 KB answer = 1
3 Correct 1 ms 2396 KB answer = 2
4 Correct 1 ms 2396 KB answer = 1
5 Correct 1 ms 2396 KB answer = 2
6 Correct 1 ms 6492 KB answer = 1
7 Correct 1 ms 6492 KB answer = 1
8 Correct 1 ms 4444 KB answer = 3
9 Correct 2 ms 8536 KB answer = 2
10 Correct 1 ms 8540 KB answer = 3
11 Correct 1 ms 6492 KB answer = 2
12 Correct 1 ms 6488 KB answer = 3
13 Correct 1 ms 8636 KB answer = 2
14 Correct 2 ms 8640 KB answer = 1
15 Correct 1 ms 6488 KB answer = 1
16 Correct 1 ms 6592 KB answer = 1
17 Correct 1 ms 6492 KB answer = 1
18 Correct 1 ms 6488 KB answer = 1
19 Correct 1 ms 6492 KB answer = 1
20 Correct 1 ms 6492 KB answer = 1
21 Correct 1 ms 6492 KB answer = 1
22 Correct 46 ms 11016 KB answer = 358
23 Correct 49 ms 11976 KB answer = 336
24 Correct 46 ms 11804 KB answer = 339
25 Correct 53 ms 11016 KB answer = 357
26 Correct 45 ms 11860 KB answer = 354
27 Correct 40 ms 11860 KB answer = 333
28 Correct 43 ms 11860 KB answer = 314
29 Correct 42 ms 11820 KB answer = 322
30 Correct 44 ms 11860 KB answer = 339
31 Correct 48 ms 11860 KB answer = 351
32 Correct 34 ms 11828 KB answer = 1
33 Correct 39 ms 11612 KB answer = 1
34 Correct 33 ms 11624 KB answer = 1
35 Correct 40 ms 11784 KB answer = 1
36 Correct 44 ms 11728 KB answer = 1
37 Correct 39 ms 6888 KB answer = 1
38 Correct 33 ms 7088 KB answer = 1
39 Correct 33 ms 7000 KB answer = 1
40 Correct 33 ms 7096 KB answer = 1
41 Correct 110 ms 3668 KB answer = 6296
42 Correct 123 ms 3620 KB answer = 6267
43 Correct 123 ms 3712 KB answer = 6264
44 Correct 117 ms 3664 KB answer = 6384
45 Correct 115 ms 3584 KB answer = 6272
46 Correct 78 ms 3664 KB answer = 6177
47 Correct 78 ms 3528 KB answer = 6144
48 Correct 84 ms 3752 KB answer = 6272
49 Correct 78 ms 3672 KB answer = 6241
50 Correct 82 ms 3564 KB answer = 6169
51 Correct 57 ms 3360 KB answer = 1
52 Correct 51 ms 3304 KB answer = 1
53 Correct 50 ms 3312 KB answer = 1
54 Correct 51 ms 3236 KB answer = 1
55 Correct 47 ms 3148 KB answer = 1
56 Correct 51 ms 3408 KB answer = 1426
57 Correct 46 ms 3436 KB answer = 1427
58 Correct 46 ms 3584 KB answer = 1428
59 Correct 46 ms 3464 KB answer = 1427
60 Execution timed out 6027 ms 15792 KB Time limit exceeded
61 Halted 0 ms 0 KB -