Submission #746211

#	Time	Username	Problem	Language	Result	Execution time	Memory
746211		PVSekhar	Longest beautiful sequence (IZhO17_subsequence)	C++14	7 / 100	129 ms	191836 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9+7;
const ll N=(1<<10);
int a[21],k[21];
int dp[N][N][11]; //prev right,cur left half,extra k to match cur left half
int ind[N][N][11]; //ind used to reach this state
int bc[N][N]; //bit count

int main()
{
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<21;k++)dp[i][j][k]=0;
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<21;k++)ind[i][j][k]=-1;
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)bc[i][j]=__builtin_popcount(i&j);

    int n;
    cin>>n;
    for (int i = 0; i < n; i++)cin>>a[i];
    for (int i = 0; i < n; i++)cin>>k[i];
    int p[n]; //stores previous index
    for(int i=0;i<n;i++)p[i]=i;
    int ans=0,ans_i,len,extra;
    for (int i = 0; i < n; i++)
    {
        int l=a[i]>>(10),r=a[i]%(N);
        // cout<<l<<" "<<r<<"\n";
        len=1;
        for (int j = 0; j < N; j++)
        {
            extra=k[i]-bc[j][r];
            if(extra<0||extra>10)continue;
            if(len<(dp[j][l][extra]+1)){
                len=dp[j][l][extra]+1;
                p[i]=ind[j][l][extra];
            }
        }
        for (int j = 0; j < N; j++)
        {
            if(len>dp[r][j][bc[j][l]]){
                dp[r][j][bc[j][l]]=len;
                ind[r][j][bc[j][l]]=i;
                // cout<<j<<"\n";
            }
        }
        if(len>ans){
            ans=len;
            ans_i=i;
        }
        // cout<<ans<<"\n";
    }
    cout<<ans<<"\n";
    vector<int> temp;
    while(p[ans_i]!=ans_i){
        temp.push_back(ans_i);
        ans_i=p[ans_i];
    }
    temp.push_back(ans_i);
    for (int i = ans-1; i >=0 ; i--)
    {
        cout<<temp[i]+1<<" ";
    }
    cout<<"\n";
    
    return 0;   
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:13:77: warning: iteration 11 invokes undefined behavior [-Waggressive-loop-optimizations]
   13 |     for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<21;k++)dp[i][j][k]=0;
      |                                                                  ~~~~~~~~~~~^~
subsequence.cpp:13:58: note: within this loop
   13 |     for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<21;k++)dp[i][j][k]=0;
      |                                                         ~^~~
subsequence.cpp:14:78: warning: iteration 11 invokes undefined behavior [-Waggressive-loop-optimizations]
   14 |     for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<21;k++)ind[i][j][k]=-1;
      |                                                                  ~~~~~~~~~~~~^~~
subsequence.cpp:14:58: note: within this loop
   14 |     for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<21;k++)ind[i][j][k]=-1;
      |                                                         ~^~~

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