oj.uz

Submission #953889

# Submission time Handle Problem Language Result Execution time Memory
953889 2024-03-26T19:31:29 Z Wael Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 5120 ms 93268 KB 
#include <bits/stdc++.h>
using namespace std;
#define log(x) (63^__builtin_clzll(x))
//#define endl '\n'
#define all(x) (x).begin() , (x).end() 
 
pair<int, int> dp[(1 << 10) + 2][(1 << 10) + 2][11];
void solve() {
    int n;
    cin >> n;
    vector<int> a(n), k(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n; ++i) cin >> k[i];
 
    int fullDown = (1 << 10) - 1, fullUp = (1 << 20) - 1 - fullDown, ans = 0, last = 0;
    vector<int> prev(n, -1);
    for(int i = 0; i < n; ++i) { 
        int mx = 1, up = ((fullUp & a[i]) >> 10), down = (fullDown & a[i]);
        for(int reqUp = 0; reqUp < (1 << 10); ++reqUp) {
            int common = __builtin_popcount((reqUp & up));
            if(k[i] >= common && k[i] - common <= 10) {
                auto state = dp[reqUp][down][k[i] - common];
                if(state.first + 1 > mx) prev[i] = state.second;
                mx = max(mx, state.first + 1);
            }
        }
        if(mx > ans) last = i;
        ans = max(ans, mx);
        for(int reqDown = 0; reqDown < (1 << 10); ++reqDown) {
            int common = __builtin_popcount((reqDown & a[i]));
            dp[up][reqDown][common] = max(dp[up][reqDown][common], {mx, i});
        }
    }
 
    vector<int> indices;
    while(last != -1) {
        indices.push_back(last);
        last = prev[last];
    }
    assert(indices.size() == ans);
    reverse(all(indices));
 
    int ok = 1;
    for(int j = 1; j < indices.size(); ++j) 
        if(__builtin_popcount(a[indices[j]] & a[indices[j - 1]]) != k[indices[j]]) ok = 0;
    if(ok == 0) {
        --ans;
        indices.pop_back();
    }
    cout << ans << endl;
 
    for(auto j : indices) cout << j + 1 << " ";
    cout << endl;
 
    return;
}
 
main() {
    ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
    
    int t = 1;
    //cin >> t;
    while(t--) solve();
    
    return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from subsequence.cpp:1:
subsequence.cpp: In function 'void solve()':
subsequence.cpp:40:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     assert(indices.size() == ans);
      |            ~~~~~~~~~~~~~~~^~~~~~
subsequence.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int j = 1; j < indices.size(); ++j)
      |                    ~~^~~~~~~~~~~~~~~~
subsequence.cpp: At global scope:
subsequence.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main() {
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB answer = 4
2 Correct 0 ms 856 KB answer = 1
3 Correct 1 ms 604 KB answer = 2
4 Correct 1 ms 348 KB answer = 1
5 Correct 1 ms 604 KB answer = 2
6 Correct 1 ms 604 KB answer = 1
7 Correct 1 ms 348 KB answer = 1
8 Correct 1 ms 1884 KB answer = 3
9 Correct 2 ms 1628 KB answer = 2
10 Correct 1 ms 1880 KB answer = 3
11 Correct 1 ms 1628 KB answer = 2
12 Correct 1 ms 2004 KB answer = 3
13 Correct 1 ms 1628 KB answer = 2
14 Correct 2 ms 1628 KB answer = 1
15 Correct 2 ms 1996 KB answer = 1
16 Correct 2 ms 1884 KB answer = 1
17 Correct 2 ms 1628 KB answer = 1
18 Correct 1 ms 860 KB answer = 1
19 Correct 1 ms 860 KB answer = 1
20 Correct 1 ms 604 KB answer = 1
21 Correct 1 ms 720 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB answer = 4
2 Correct 0 ms 856 KB answer = 1
3 Correct 1 ms 604 KB answer = 2
4 Correct 1 ms 348 KB answer = 1
5 Correct 1 ms 604 KB answer = 2
6 Correct 1 ms 604 KB answer = 1
7 Correct 1 ms 348 KB answer = 1
8 Correct 1 ms 1884 KB answer = 3
9 Correct 2 ms 1628 KB answer = 2
10 Correct 1 ms 1880 KB answer = 3
11 Correct 1 ms 1628 KB answer = 2
12 Correct 1 ms 2004 KB answer = 3
13 Correct 1 ms 1628 KB answer = 2
14 Correct 2 ms 1628 KB answer = 1
15 Correct 2 ms 1996 KB answer = 1
16 Correct 2 ms 1884 KB answer = 1
17 Correct 2 ms 1628 KB answer = 1
18 Correct 1 ms 860 KB answer = 1
19 Correct 1 ms 860 KB answer = 1
20 Correct 1 ms 604 KB answer = 1
21 Correct 1 ms 720 KB answer = 1
22 Correct 179 ms 90196 KB answer = 358
23 Correct 178 ms 90448 KB answer = 336
24 Correct 182 ms 90036 KB answer = 339
25 Correct 199 ms 90452 KB answer = 357
26 Correct 187 ms 90448 KB answer = 354
27 Correct 170 ms 84304 KB answer = 333
28 Correct 194 ms 85284 KB answer = 314
29 Correct 171 ms 84560 KB answer = 322
30 Correct 172 ms 85628 KB answer = 339
31 Correct 176 ms 84308 KB answer = 351
32 Correct 255 ms 86360 KB answer = 1
33 Correct 248 ms 85928 KB answer = 1
34 Correct 257 ms 85588 KB answer = 1
35 Correct 249 ms 86100 KB answer = 1
36 Correct 242 ms 85396 KB answer = 1
37 Correct 52 ms 4944 KB answer = 1
38 Correct 49 ms 4948 KB answer = 1
39 Correct 52 ms 4916 KB answer = 1
40 Correct 56 ms 4744 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB answer = 4
2 Correct 0 ms 856 KB answer = 1
3 Correct 1 ms 604 KB answer = 2
4 Correct 1 ms 348 KB answer = 1
5 Correct 1 ms 604 KB answer = 2
6 Correct 1 ms 604 KB answer = 1
7 Correct 1 ms 348 KB answer = 1
8 Correct 1 ms 1884 KB answer = 3
9 Correct 2 ms 1628 KB answer = 2
10 Correct 1 ms 1880 KB answer = 3
11 Correct 1 ms 1628 KB answer = 2
12 Correct 1 ms 2004 KB answer = 3
13 Correct 1 ms 1628 KB answer = 2
14 Correct 2 ms 1628 KB answer = 1
15 Correct 2 ms 1996 KB answer = 1
16 Correct 2 ms 1884 KB answer = 1
17 Correct 2 ms 1628 KB answer = 1
18 Correct 1 ms 860 KB answer = 1
19 Correct 1 ms 860 KB answer = 1
20 Correct 1 ms 604 KB answer = 1
21 Correct 1 ms 720 KB answer = 1
22 Correct 179 ms 90196 KB answer = 358
23 Correct 178 ms 90448 KB answer = 336
24 Correct 182 ms 90036 KB answer = 339
25 Correct 199 ms 90452 KB answer = 357
26 Correct 187 ms 90448 KB answer = 354
27 Correct 170 ms 84304 KB answer = 333
28 Correct 194 ms 85284 KB answer = 314
29 Correct 171 ms 84560 KB answer = 322
30 Correct 172 ms 85628 KB answer = 339
31 Correct 176 ms 84308 KB answer = 351
32 Correct 255 ms 86360 KB answer = 1
33 Correct 248 ms 85928 KB answer = 1
34 Correct 257 ms 85588 KB answer = 1
35 Correct 249 ms 86100 KB answer = 1
36 Correct 242 ms 85396 KB answer = 1
37 Correct 52 ms 4944 KB answer = 1
38 Correct 49 ms 4948 KB answer = 1
39 Correct 52 ms 4916 KB answer = 1
40 Correct 56 ms 4744 KB answer = 1
41 Correct 812 ms 2492 KB answer = 6296
42 Correct 824 ms 2488 KB answer = 6267
43 Correct 824 ms 2488 KB answer = 6264
44 Correct 814 ms 2644 KB answer = 6384
45 Correct 828 ms 2492 KB answer = 6272
46 Correct 810 ms 2504 KB answer = 6177
47 Correct 805 ms 2504 KB answer = 6144
48 Correct 869 ms 2644 KB answer = 6272
49 Correct 831 ms 2516 KB answer = 6241
50 Correct 844 ms 2640 KB answer = 6169
51 Correct 668 ms 2592 KB answer = 1
52 Correct 667 ms 2644 KB answer = 1
53 Correct 657 ms 2396 KB answer = 1
54 Correct 653 ms 2392 KB answer = 1
55 Correct 671 ms 2540 KB answer = 1
56 Correct 1010 ms 2444 KB answer = 1426
57 Correct 1026 ms 2448 KB answer = 1427
58 Correct 966 ms 2640 KB answer = 1428
59 Correct 1006 ms 2640 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB answer = 4
2 Correct 0 ms 856 KB answer = 1
3 Correct 1 ms 604 KB answer = 2
4 Correct 1 ms 348 KB answer = 1
5 Correct 1 ms 604 KB answer = 2
6 Correct 1 ms 604 KB answer = 1
7 Correct 1 ms 348 KB answer = 1
8 Correct 1 ms 1884 KB answer = 3
9 Correct 2 ms 1628 KB answer = 2
10 Correct 1 ms 1880 KB answer = 3
11 Correct 1 ms 1628 KB answer = 2
12 Correct 1 ms 2004 KB answer = 3
13 Correct 1 ms 1628 KB answer = 2
14 Correct 2 ms 1628 KB answer = 1
15 Correct 2 ms 1996 KB answer = 1
16 Correct 2 ms 1884 KB answer = 1
17 Correct 2 ms 1628 KB answer = 1
18 Correct 1 ms 860 KB answer = 1
19 Correct 1 ms 860 KB answer = 1
20 Correct 1 ms 604 KB answer = 1
21 Correct 1 ms 720 KB answer = 1
22 Correct 179 ms 90196 KB answer = 358
23 Correct 178 ms 90448 KB answer = 336
24 Correct 182 ms 90036 KB answer = 339
25 Correct 199 ms 90452 KB answer = 357
26 Correct 187 ms 90448 KB answer = 354
27 Correct 170 ms 84304 KB answer = 333
28 Correct 194 ms 85284 KB answer = 314
29 Correct 171 ms 84560 KB answer = 322
30 Correct 172 ms 85628 KB answer = 339
31 Correct 176 ms 84308 KB answer = 351
32 Correct 255 ms 86360 KB answer = 1
33 Correct 248 ms 85928 KB answer = 1
34 Correct 257 ms 85588 KB answer = 1
35 Correct 249 ms 86100 KB answer = 1
36 Correct 242 ms 85396 KB answer = 1
37 Correct 52 ms 4944 KB answer = 1
38 Correct 49 ms 4948 KB answer = 1
39 Correct 52 ms 4916 KB answer = 1
40 Correct 56 ms 4744 KB answer = 1
41 Correct 812 ms 2492 KB answer = 6296
42 Correct 824 ms 2488 KB answer = 6267
43 Correct 824 ms 2488 KB answer = 6264
44 Correct 814 ms 2644 KB answer = 6384
45 Correct 828 ms 2492 KB answer = 6272
46 Correct 810 ms 2504 KB answer = 6177
47 Correct 805 ms 2504 KB answer = 6144
48 Correct 869 ms 2644 KB answer = 6272
49 Correct 831 ms 2516 KB answer = 6241
50 Correct 844 ms 2640 KB answer = 6169
51 Correct 668 ms 2592 KB answer = 1
52 Correct 667 ms 2644 KB answer = 1
53 Correct 657 ms 2396 KB answer = 1
54 Correct 653 ms 2392 KB answer = 1
55 Correct 671 ms 2540 KB answer = 1
56 Correct 1010 ms 2444 KB answer = 1426
57 Correct 1026 ms 2448 KB answer = 1427
58 Correct 966 ms 2640 KB answer = 1428
59 Correct 1006 ms 2640 KB answer = 1427
60 Correct 3213 ms 93012 KB answer = 7034
61 Correct 3240 ms 93268 KB answer = 7045
62 Correct 3222 ms 93020 KB answer = 7147
63 Correct 3363 ms 93020 KB answer = 7038
64 Correct 3309 ms 93016 KB answer = 7169
65 Correct 3276 ms 93028 KB answer = 6735
66 Correct 3267 ms 92688 KB answer = 6713
67 Correct 3303 ms 92856 KB answer = 6748
68 Correct 3287 ms 92688 KB answer = 6607
69 Correct 3326 ms 92696 KB answer = 6722
70 Correct 4926 ms 93232 KB answer = 1
71 Correct 5120 ms 93000 KB answer = 1
72 Correct 5077 ms 92896 KB answer = 1
73 Correct 5108 ms 92984 KB answer = 1
74 Correct 5021 ms 92968 KB answer = 1
75 Correct 1845 ms 52072 KB answer = 1
76 Correct 1895 ms 52384 KB answer = 1
77 Correct 1756 ms 52436 KB answer = 1
78 Correct 1751 ms 51900 KB answer = 1
79 Correct 1624 ms 37220 KB answer = 21
80 Correct 2299 ms 59368 KB answer = 7
81 Correct 2959 ms 77784 KB answer = 3
82 Correct 2961 ms 88396 KB answer = 2
83 Correct 2443 ms 80252 KB answer = 1
84 Correct 1919 ms 61932 KB answer = 1
85 Correct 1705 ms 52156 KB answer = 1
86 Correct 1462 ms 37252 KB answer = 11
87 Correct 2103 ms 59456 KB answer = 11
88 Correct 2787 ms 78328 KB answer = 6
89 Correct 2923 ms 88220 KB answer = 4
90 Correct 2434 ms 80280 KB answer = 2
91 Correct 1936 ms 61940 KB answer = 2
92 Correct 1679 ms 52168 KB answer = 2
93 Correct 3256 ms 93024 KB answer = 7211
94 Correct 3257 ms 93028 KB answer = 7032
95 Correct 3304 ms 93024 KB answer = 7092
96 Correct 4431 ms 92892 KB answer = 14167
97 Correct 4396 ms 92980 KB answer = 14159
98 Correct 4461 ms 92980 KB answer = 14125
99 Correct 4383 ms 92988 KB answer = 14121
100 Correct 4273 ms 92984 KB answer = 14010
101 Correct 4317 ms 92980 KB answer = 13976
102 Correct 1710 ms 52080 KB answer = 3
103 Correct 1998 ms 62308 KB answer = 2
104 Correct 2478 ms 80352 KB answer = 3
105 Correct 1615 ms 51400 KB answer = 2
106 Correct 1638 ms 61912 KB answer = 3
107 Correct 1998 ms 88292 KB answer = 4
108 Correct 1835 ms 77912 KB answer = 5
109 Correct 1352 ms 59796 KB answer = 8
110 Correct 1029 ms 37460 KB answer = 22
111 Correct 3281 ms 93096 KB answer = 6760
112 Correct 3352 ms 93032 KB answer = 6788
113 Correct 3296 ms 92952 KB answer = 6632