Submission #173014

#	Time	Username	Problem	Language	Result	Execution time	Memory
173014		juggernaut	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	2 ms	376 KiB

subsequence

//Just try and the idea will come!
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int n,i,a[100001],k[100001],dp[100001],j,path[100001],mx,ind,m[(1ll<<20)],pos[(1ll<<20)];
vector<int>ans;
main(){
    scanf("%lld",&n);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(i=1;i<=n;i++)scanf("%lld",&k[i]),dp[i]=1,m[a[i]]=1,pos[a[i]]=i;
    for(i=1;i<=n;i++){
        for(j=1;j<(1ll<<8);j++)
            if(__builtin_popcount(a[i]&j)==k[i]&&m[j]+1>dp[i]){
                dp[i]=m[j]+1;
                path[i]=pos[j];
            }
        if(dp[i]>m[a[i]]){
            m[a[i]]=dp[i];
            pos[a[i]]=i;
        }
        if(dp[i]>mx){
            mx=dp[i];
            ind=i;
        }
    }
    do{
        ans.push_back(ind);
        ind=path[ind];
    }while(ind!=0);
    reverse(ans.begin(),ans.end());
    printf("%lld\n",(int)(ans.size()));
    for(int res:ans)printf("%lld ",res);
}

Compilation message (stderr)

subsequence.cpp:7:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
subsequence.cpp:9:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++)scanf("%lld",&a[i]);
                      ~~~~~^~~~~~~~~~~~~~
subsequence.cpp:10:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++)scanf("%lld",&k[i]),dp[i]=1,m[a[i]]=1,pos[a[i]]=i;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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