Submission #1006349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006349		milisav	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2099 ms	54980 KiB

subsequence

#include <bits/stdc++.h>
#define maxn 200000
#define maxv 2000000
using namespace std;
int n;
int a[maxn];
int k[maxn];
int len[maxn];
int prv[maxn];
int msk=(1<<10)-1;
int lmsk=msk<<10;
int bst[maxv][12];
int query(int a,int k) {
    int u,l;
    u=a&lmsk;
    l=a&msk;
    int ret=0;
    for(int j=0;j<=msk;j++) {
        int v=__builtin_popcount(l&j);
        if(v<=k && k-v<=10 && len[bst[u|j][k-v]]>len[ret]) {
            ret=bst[u|j][k-v];
        }
    }
    return ret;
}
void update(int a,int v) {
    int u,l;
    u=a&lmsk;
    l=a&msk;
    for(int j=0;j<=msk;j++) {
        int d=j<<10;
        int c=__builtin_popcount(u&d);
        if(len[v]>len[bst[d|l][c]]) {
            bst[d|l][c]=v;
        }
    }
}
vector<int> c;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++) {
        cin>>k[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++) {
        int v=query(a[i],k[i]);
        prv[i]=v;
        len[i]=len[v]+1;
        update(a[i],i);
        if(len[i]>len[ans]) ans=i;
    }
    while(ans!=0) {
        c.push_back(ans);
        ans=prv[ans];
    }
    reverse(c.begin(),c.end());
    cout<<c.size()<<endl;
    for(auto x:c) {
        cout<<x<<" ";
    }
    return 0;
}

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