oj.uz

Submission #953905

# Submission time Handle Problem Language Result Execution time Memory
953905 2024-03-26T21:13:46 Z Wael Longest beautiful sequence (IZhO17_subsequence) C++14
40 / 100
 6000 ms 125720 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() 
 
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);
    int M = 1 << 10;
    vector<vector<vector<pair<int, int>>>> dp(M, vector<vector<pair<int, int>>>(M, vector<pair<int, int>>(11, {0, 0})));
    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));
 
    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:41:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     assert(indices.size() == ans);
      |            ~~~~~~~~~~~~~~~^~~~~~
subsequence.cpp: At global scope:
subsequence.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main() {
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 123712 KB answer = 4
2 Correct 77 ms 123472 KB answer = 1
3 Correct 76 ms 123672 KB answer = 2
4 Correct 78 ms 123516 KB answer = 1
5 Correct 76 ms 123580 KB answer = 2
6 Correct 77 ms 123476 KB answer = 1
7 Correct 80 ms 123476 KB answer = 1
8 Correct 94 ms 123472 KB answer = 3
9 Correct 77 ms 123472 KB answer = 2
10 Correct 77 ms 123568 KB answer = 3
11 Correct 77 ms 123476 KB answer = 2
12 Correct 84 ms 123728 KB answer = 3
13 Correct 88 ms 123516 KB answer = 2
14 Correct 75 ms 123508 KB answer = 1
15 Correct 76 ms 123696 KB answer = 1
16 Correct 84 ms 123728 KB answer = 1
17 Correct 88 ms 123472 KB answer = 1
18 Correct 75 ms 123472 KB answer = 1
19 Correct 77 ms 123476 KB answer = 1
20 Correct 77 ms 123680 KB answer = 1
21 Correct 77 ms 123476 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 123712 KB answer = 4
2 Correct 77 ms 123472 KB answer = 1
3 Correct 76 ms 123672 KB answer = 2
4 Correct 78 ms 123516 KB answer = 1
5 Correct 76 ms 123580 KB answer = 2
6 Correct 77 ms 123476 KB answer = 1
7 Correct 80 ms 123476 KB answer = 1
8 Correct 94 ms 123472 KB answer = 3
9 Correct 77 ms 123472 KB answer = 2
10 Correct 77 ms 123568 KB answer = 3
11 Correct 77 ms 123476 KB answer = 2
12 Correct 84 ms 123728 KB answer = 3
13 Correct 88 ms 123516 KB answer = 2
14 Correct 75 ms 123508 KB answer = 1
15 Correct 76 ms 123696 KB answer = 1
16 Correct 84 ms 123728 KB answer = 1
17 Correct 88 ms 123472 KB answer = 1
18 Correct 75 ms 123472 KB answer = 1
19 Correct 77 ms 123476 KB answer = 1
20 Correct 77 ms 123680 KB answer = 1
21 Correct 77 ms 123476 KB answer = 1
22 Correct 386 ms 123728 KB answer = 358
23 Correct 372 ms 123812 KB answer = 336
24 Correct 356 ms 123816 KB answer = 339
25 Correct 361 ms 123988 KB answer = 357
26 Correct 368 ms 123732 KB answer = 354
27 Correct 358 ms 123984 KB answer = 333
28 Correct 375 ms 123820 KB answer = 314
29 Correct 360 ms 123984 KB answer = 322
30 Correct 354 ms 123728 KB answer = 339
31 Correct 363 ms 123812 KB answer = 351
32 Correct 507 ms 123812 KB answer = 1
33 Correct 486 ms 123736 KB answer = 1
34 Correct 489 ms 123820 KB answer = 1
35 Correct 498 ms 123984 KB answer = 1
36 Correct 521 ms 123704 KB answer = 1
37 Correct 448 ms 123988 KB answer = 1
38 Correct 466 ms 123732 KB answer = 1
39 Correct 442 ms 123828 KB answer = 1
40 Correct 468 ms 124048 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 123712 KB answer = 4
2 Correct 77 ms 123472 KB answer = 1
3 Correct 76 ms 123672 KB answer = 2
4 Correct 78 ms 123516 KB answer = 1
5 Correct 76 ms 123580 KB answer = 2
6 Correct 77 ms 123476 KB answer = 1
7 Correct 80 ms 123476 KB answer = 1
8 Correct 94 ms 123472 KB answer = 3
9 Correct 77 ms 123472 KB answer = 2
10 Correct 77 ms 123568 KB answer = 3
11 Correct 77 ms 123476 KB answer = 2
12 Correct 84 ms 123728 KB answer = 3
13 Correct 88 ms 123516 KB answer = 2
14 Correct 75 ms 123508 KB answer = 1
15 Correct 76 ms 123696 KB answer = 1
16 Correct 84 ms 123728 KB answer = 1
17 Correct 88 ms 123472 KB answer = 1
18 Correct 75 ms 123472 KB answer = 1
19 Correct 77 ms 123476 KB answer = 1
20 Correct 77 ms 123680 KB answer = 1
21 Correct 77 ms 123476 KB answer = 1
22 Correct 386 ms 123728 KB answer = 358
23 Correct 372 ms 123812 KB answer = 336
24 Correct 356 ms 123816 KB answer = 339
25 Correct 361 ms 123988 KB answer = 357
26 Correct 368 ms 123732 KB answer = 354
27 Correct 358 ms 123984 KB answer = 333
28 Correct 375 ms 123820 KB answer = 314
29 Correct 360 ms 123984 KB answer = 322
30 Correct 354 ms 123728 KB answer = 339
31 Correct 363 ms 123812 KB answer = 351
32 Correct 507 ms 123812 KB answer = 1
33 Correct 486 ms 123736 KB answer = 1
34 Correct 489 ms 123820 KB answer = 1
35 Correct 498 ms 123984 KB answer = 1
36 Correct 521 ms 123704 KB answer = 1
37 Correct 448 ms 123988 KB answer = 1
38 Correct 466 ms 123732 KB answer = 1
39 Correct 442 ms 123828 KB answer = 1
40 Correct 468 ms 124048 KB answer = 1
41 Correct 3665 ms 125460 KB answer = 6296
42 Correct 3460 ms 125448 KB answer = 6267
43 Correct 3537 ms 125412 KB answer = 6264
44 Correct 3638 ms 125416 KB answer = 6384
45 Correct 3583 ms 125264 KB answer = 6272
46 Correct 3187 ms 125412 KB answer = 6177
47 Correct 3372 ms 125416 KB answer = 6144
48 Correct 3225 ms 125412 KB answer = 6272
49 Correct 3005 ms 125264 KB answer = 6241
50 Correct 3172 ms 125416 KB answer = 6169
51 Correct 805 ms 125416 KB answer = 1
52 Correct 818 ms 125412 KB answer = 1
53 Correct 819 ms 125320 KB answer = 1
54 Correct 777 ms 125268 KB answer = 1
55 Correct 791 ms 125416 KB answer = 1
56 Correct 4462 ms 125416 KB answer = 1426
57 Correct 3988 ms 125416 KB answer = 1427
58 Correct 4321 ms 125416 KB answer = 1428
59 Correct 4444 ms 125412 KB answer = 1427

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 123712 KB answer = 4
2 Correct 77 ms 123472 KB answer = 1
3 Correct 76 ms 123672 KB answer = 2
4 Correct 78 ms 123516 KB answer = 1
5 Correct 76 ms 123580 KB answer = 2
6 Correct 77 ms 123476 KB answer = 1
7 Correct 80 ms 123476 KB answer = 1
8 Correct 94 ms 123472 KB answer = 3
9 Correct 77 ms 123472 KB answer = 2
10 Correct 77 ms 123568 KB answer = 3
11 Correct 77 ms 123476 KB answer = 2
12 Correct 84 ms 123728 KB answer = 3
13 Correct 88 ms 123516 KB answer = 2
14 Correct 75 ms 123508 KB answer = 1
15 Correct 76 ms 123696 KB answer = 1
16 Correct 84 ms 123728 KB answer = 1
17 Correct 88 ms 123472 KB answer = 1
18 Correct 75 ms 123472 KB answer = 1
19 Correct 77 ms 123476 KB answer = 1
20 Correct 77 ms 123680 KB answer = 1
21 Correct 77 ms 123476 KB answer = 1
22 Correct 386 ms 123728 KB answer = 358
23 Correct 372 ms 123812 KB answer = 336
24 Correct 356 ms 123816 KB answer = 339
25 Correct 361 ms 123988 KB answer = 357
26 Correct 368 ms 123732 KB answer = 354
27 Correct 358 ms 123984 KB answer = 333
28 Correct 375 ms 123820 KB answer = 314
29 Correct 360 ms 123984 KB answer = 322
30 Correct 354 ms 123728 KB answer = 339
31 Correct 363 ms 123812 KB answer = 351
32 Correct 507 ms 123812 KB answer = 1
33 Correct 486 ms 123736 KB answer = 1
34 Correct 489 ms 123820 KB answer = 1
35 Correct 498 ms 123984 KB answer = 1
36 Correct 521 ms 123704 KB answer = 1
37 Correct 448 ms 123988 KB answer = 1
38 Correct 466 ms 123732 KB answer = 1
39 Correct 442 ms 123828 KB answer = 1
40 Correct 468 ms 124048 KB answer = 1
41 Correct 3665 ms 125460 KB answer = 6296
42 Correct 3460 ms 125448 KB answer = 6267
43 Correct 3537 ms 125412 KB answer = 6264
44 Correct 3638 ms 125416 KB answer = 6384
45 Correct 3583 ms 125264 KB answer = 6272
46 Correct 3187 ms 125412 KB answer = 6177
47 Correct 3372 ms 125416 KB answer = 6144
48 Correct 3225 ms 125412 KB answer = 6272
49 Correct 3005 ms 125264 KB answer = 6241
50 Correct 3172 ms 125416 KB answer = 6169
51 Correct 805 ms 125416 KB answer = 1
52 Correct 818 ms 125412 KB answer = 1
53 Correct 819 ms 125320 KB answer = 1
54 Correct 777 ms 125268 KB answer = 1
55 Correct 791 ms 125416 KB answer = 1
56 Correct 4462 ms 125416 KB answer = 1426
57 Correct 3988 ms 125416 KB answer = 1427
58 Correct 4321 ms 125416 KB answer = 1428
59 Correct 4444 ms 125412 KB answer = 1427
60 Correct 5587 ms 125672 KB answer = 7034
61 Correct 5648 ms 125672 KB answer = 7045
62 Correct 5397 ms 125720 KB answer = 7147
63 Correct 5418 ms 125664 KB answer = 7038
64 Correct 5557 ms 125672 KB answer = 7169
65 Correct 5633 ms 125672 KB answer = 6735
66 Correct 5272 ms 125672 KB answer = 6713
67 Correct 5407 ms 125672 KB answer = 6748
68 Correct 5325 ms 125664 KB answer = 6607
69 Correct 5394 ms 125680 KB answer = 6722
70 Execution timed out 6009 ms 125520 KB Time limit exceeded
71 Halted 0 ms 0 KB -