Submission #1345880

#TimeUsernameProblemLanguageResultExecution timeMemory
1345880OwstinLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
38 ms99420 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define umap unordered_map
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n; cin >> n;
    vector<pair<int, int>> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i].first;
    }
    for (int i = 0; i < n; i++) {
        cin >> vec[i].second;
    }
    int block = 10;
    vector<int> last(n);
    vector<vector<vector<pair<int, int>>>> dp(block + 1, vector<vector<pair<int, int>>>(1 << block, vector<pair<int, int>>(1 << block)));
    pair<int, int> res = {0, 0};
    for (int i = 0; i < n; i++) {
        pair<int, int> curr = {0, -1}; int t = vec[i].first >> block; int s = vec[i].first & ((1 << 10) - 1);
        for (int j = 0; j <= min(block, vec[i].second); j++) {
            for (int k = 0; k < 1 << block; k++) {
                int match = __builtin_popcount(k & vec[i].first);
                if (match + j == vec[i].second) {
                    curr = max(curr, dp[j][t][k]);
                }
            }
        }
        last[i] = curr.second;
        res = max(res, {curr.first + 1, i});
        for (int j = 0; j <= block; j++) {
            int match = __builtin_popcount(t & j);
            dp[match][j][s] = max(dp[match][j][s], {curr.first + 1, i});
        }
    }
    cout << res.first << endl;
    vector<int> recon;
    while (recon.size() != res.first) {
        recon.pb(res.second);
        res.second = last[res.second];
    }
    reverse(all(recon));
    for (auto x : recon) {
        cout << x + 1 << space;
    }
}

int main() {
    FAST_IO;
    //freopen("guard.in", "r", stdin);
    //freopen("guard.out", "w", stdout);
    //TEST_CASES;
    solve(); cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...