Submission #333551

#	Time	Username	Problem	Language	Result	Execution time	Memory
333551		juggernaut	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	127 ms	1900 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005],i,dp[1<<21],mx,c[100005],path[100005],x,mask[256];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        c[i]=1;
        if(n<5001){
            for(int j=1;j<i;j++){
                if(__builtin_popcount(a[j]&a[i])==b[i]&&c[i]<c[j]+1){
                    c[i]=c[j]+1;
                    path[i]=j;
                }
            }
        }else{
            for(int j=0;j<256;j++){
                int tmp=mask[j];
                if(__builtin_popcount(a[tmp]&a[i])==b[i]&&c[i]<c[tmp]+1){
                    c[i]=c[tmp]+1;
                    path[i]=tmp;
                }
            }
            mask[a[i]]=i;
        }
        if(c[i]>mx){
            mx=c[i];
            x=i;
        }
    }
    printf("%d\n",mx);
    stack<int>st;
    while(x){
        st.push(x);
        x=path[x];
    }
    while(!st.empty()){
        printf("%d ",st.top());
        st.pop();
    }
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:5:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    5 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
subsequence.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    6 |     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
subsequence.cpp:7:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |     for(int i=1;i<=n;i++)scanf("%d",&b[i]);
      |                          ~~~~~^~~~~~~~~~~~

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