Submission #866671

#	Time	Username	Problem	Language	Result	Execution time	Memory
866671		Dec0Dedd	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6020 ms	174760 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5+10;
const int K = 1024;
const int X = 10;

int p[N], a[N], x[N], n;
pii dp[K][K][2*X+1];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>n;
    for (int i=1; i<=n; ++i) cin>>a[i];
    for (int i=1; i<=n; ++i) cin>>x[i];

    pii ans={1, 1};
    for (int i=1; i<=n; ++i) {
        int lf=a[i]&((1<<X)-1), rf=((a[i]>>X)&((1<<X)-1));

        pii mx={0, 0};
        for (int lms=0; lms<K; ++lms) {
            int v=x[i]-__builtin_popcount(lms&lf);
            if (v < 0) continue;
            mx=max(mx, dp[lms][rf][v]);
        } p[i]=mx.second;

        for (int rms=0; rms<K; ++rms) {
            int v=__builtin_popcount(rms&rf);
            dp[lf][rms][v]=max(dp[lf][rms][v], {mx.first+1, i});
        }
        ans=max(ans, {mx.first+1, i});
    }

    vector<int> v;
    int g=ans.second;
    while (g != 0) v.push_back(g), g=p[g];
    reverse(v.begin(), v.end());

    for (int i=1; i<ans.first; ++i) {
        assert(__builtin_popcount(a[v[i]]&a[v[i-1]]) == x[v[i]]);
    }

    assert((int)v.size() == ans.first);
    cout<<ans.first<<"\n";
    for (auto u : v) cout<<u<<" ";
    cout<<"\n";
}

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 60