oj.uz

Submission #953764

# Submission time Handle Problem Language Result Execution time Memory
953764 2024-03-26T15:38:37 Z Wael Longest beautiful sequence (IZhO17_subsequence) C++17
0 / 100
 2 ms 1884 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) {
                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;
}
/*
1 1 1 1
0 1 1 0
0 1 0 1
0 1 0 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB answer = 4
2 Correct 1 ms 604 KB answer = 1
3 Correct 1 ms 604 KB answer = 2
4 Correct 0 ms 600 KB answer = 1
5 Correct 0 ms 604 KB answer = 2
6 Correct 1 ms 860 KB answer = 1
7 Correct 0 ms 604 KB answer = 1
8 Correct 2 ms 1884 KB answer = 3
9 Incorrect 1 ms 1628 KB there is incorrect path (3, 5)
10 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB answer = 4
2 Correct 1 ms 604 KB answer = 1
3 Correct 1 ms 604 KB answer = 2
4 Correct 0 ms 600 KB answer = 1
5 Correct 0 ms 604 KB answer = 2
6 Correct 1 ms 860 KB answer = 1
7 Correct 0 ms 604 KB answer = 1
8 Correct 2 ms 1884 KB answer = 3
9 Incorrect 1 ms 1628 KB there is incorrect path (3, 5)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB answer = 4
2 Correct 1 ms 604 KB answer = 1
3 Correct 1 ms 604 KB answer = 2
4 Correct 0 ms 600 KB answer = 1
5 Correct 0 ms 604 KB answer = 2
6 Correct 1 ms 860 KB answer = 1
7 Correct 0 ms 604 KB answer = 1
8 Correct 2 ms 1884 KB answer = 3
9 Incorrect 1 ms 1628 KB there is incorrect path (3, 5)
10 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB answer = 4
2 Correct 1 ms 604 KB answer = 1
3 Correct 1 ms 604 KB answer = 2
4 Correct 0 ms 600 KB answer = 1
5 Correct 0 ms 604 KB answer = 2
6 Correct 1 ms 860 KB answer = 1
7 Correct 0 ms 604 KB answer = 1
8 Correct 2 ms 1884 KB answer = 3
9 Incorrect 1 ms 1628 KB there is incorrect path (3, 5)
10 Halted 0 ms 0 KB -