Submission #1227221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227221		Almonther	Longest beautiful sequence (IZhO17_subsequence)	C++20	40 / 100	70 ms	5956 KiB

subsequence

#include<bits/stdc++.h>

#define ll long long
#define co cout<<

using namespace std;
// stuff
const int maxn=1e5+5,maxa=1e6+5;
ll valgroup[maxa],mxgroup[maxa];
ll arr[maxn],val[maxn],par[maxn],k[maxn];
vector<ll>ans;
void ret(ll node){
    if(par[node]!=-1) ret(par[node]);
    ans.push_back(node);
}
void solve(){
    ll n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<n;i++) cin>>k[i];
    pair<ll,ll>mx={0,0};
    if(n<=5000){
        for(int i=0;i<n;i++){
            val[i]=1;
            par[i]=-1;
            for(int j=0;j<i;j++){
                if(val[j]+1>val[i]&&__popcount(arr[i]&arr[j])==k[i]){
                    val[i]=val[j]+1,par[i]=j,mx=max(mx,{val[i],i});
                }
            }
        }
    }
    else{
        for(int i=0;i<n;i++){
            val[i]=1;
            par[i]=-1;
            for(int j=0;j<(1<<8);j++){
                if(__popcount(j&arr[i])==k[i]){
                    if(valgroup[j]+1>val[i]){
                        val[i]=valgroup[j]+1,mx=max(mx,{val[i],i}),par[i]=mxgroup[j];
                    }
                }
            }
            if(valgroup[arr[i]]<val[i]){
                valgroup[arr[i]]=val[i];
                mxgroup[arr[i]]=i;
            }
        }
    }
    ret(mx.second);
    co ans.size()<<'\n';
    for(auto i:ans) co i+1<<' ';
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--) solve();
}

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