Submission #842727

#TimeUsernameProblemLanguageResultExecution timeMemory
842727zwezdinvLongest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
3367 ms48212 KiB
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()

const int Q = 1 << 10;
const int N = 1e5;

int n, a[N], k[N];
int dp[N], par[N];
int mx[Q][Q][11];

int qmx(int i, int j) {
    if (i == -1) return j;
    if (j == -1) return i;
    return dp[i] > dp[j] ? i : j;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> k[i];
    for (int i = 0; i < n; ++i) {
        dp[i] = 1;
        par[i] = -1;
    }
    for (int i = 0; i < Q; ++i) {
        for (int j = 0; j < Q; ++j) {
            for (int c = 0; c <= 10; ++c) {
                mx[i][j][c] = -1;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        int x = a[i] / Q, y = a[i] % Q;
        for (int j = 0; j < Q; ++j) {
            int q = k[i] - __builtin_popcount(x & j);
            if (q < 0 || q > 10) continue;
            par[i] = qmx(par[i], mx[j][y][q]);
        }
        if (par[i] != -1) dp[i] = dp[par[i]] + 1;
        for (int j = 0; j < Q; ++j) {
            int q = __builtin_popcount(y & j);
            mx[x][j][q] = qmx(mx[x][j][q], i);
        }
    }
    vector<int> ans;
    int u = max_element(dp, dp + n) - dp;
    while (u != -1) {
        ans.push_back(u);
        u = par[u];
    }
    reverse(all(ans));
    cout << ans.size() << '\n';
    for (auto i : ans) cout << i + 1 << ' ';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...