Submission #173055

#	Time	Username	Problem	Language	Result	Execution time	Memory
173055		juggernaut	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3493 ms	83476 KiB

subsequence

//Just try and the idea will come!
#include<bits/stdc++.h>
using namespace std;
int a[100001],k[100001],cnt[1025],dp[21][1025][1025],pos[21][1025][1025],path[100001],n,i,x,y,res,j,tmp,mx,ind;
vector<int>ans;
main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=n;i++)scanf("%d",&k[i]);
    for(i=1;i<1025;i++)cnt[i]=__builtin_popcount(i);
    for(i=1;i<=n;i++){
        x=(a[i]>>10);
        y=a[i]-(x<<10);
        path[i]=i;
        res=1;
        for(j=0;j<1025;j++){
            tmp=cnt[j&y];
            if(tmp<=k[i]&&k[i]-tmp<11&&dp[k[i]-tmp][j][x]+1>res){
                res=dp[k[i]-tmp][j][x]+1;
                path[i]=pos[k[i]-tmp][j][x];
            }
        }
        if(res>mx){
            mx=res;
            ind=i;
        }
        for(j=0;j<1025;j++){
            tmp=cnt[x&j];
            if(dp[tmp][y][j]<res){
                dp[tmp][y][j]=res;
                pos[tmp][y][j]=i;
            }
        }
    }
    while(path[ind]!=ind){
        ans.push_back(ind);
        ind=path[ind];
    }
    ans.push_back(ind);
    reverse(ans.begin(),ans.end());
    printf("%d\n",(int)ans.size());
    for(int to:ans)printf("%d ",to);
}

Compilation message (stderr)

subsequence.cpp:6:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
subsequence.cpp:8: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("%d",&a[i]);
                      ~~~~~^~~~~~~~~~~~
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("%d",&k[i]);
                      ~~~~~^~~~~~~~~~~~

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