Submission #89921

#	Time	Username	Problem	Language	Result	Execution time	Memory
89921		Bodo171	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	8 ms	6392 KiB

subsequence

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=(1<<17);
const int valmax=(1<<20)+1;
const int lim=(1<<10);
vector<int> seq;
int dp[valmax][22][11];
int v[nmax],k[nmax],best[nmax];
int pc[lim+5];
int n,i,j,ans,curr;
void ins(int x,int val)
{
    for(int i=0;i<lim;i++)
        dp[(x^i)][pc[x]][pc[i]]=max(dp[(x^i)][pc[x]][pc[i]],val);
}
int gt(int x,int b,int btot)
{
    int ret=0;
    for(int i=0;i<lim;i++)
        for(j=0;j<=20;j++)
            if(btot+j-pc[i]-2*b>=0&&btot+j-pc[i]-2*b<=10)
               ret=max(ret,dp[(x^(i<<10))][j][btot+j-pc[i]-2*b]);
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<(1<<20);i++)
       pc[i]=pc[(i&(i-1))]+1;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(i=1;i<=n;i++)
    {
        cin>>k[i];
    }
    for(int cnt=1;cnt<=n;cnt++)
    {
        best[cnt]=gt(v[cnt],k[cnt],pc[v[cnt]])+1;
        ins(v[cnt],best[cnt]);
        ans=max(ans,best[cnt]);
        if(ans==best[cnt])
            curr=cnt;
    }
    cout<<ans<<'\n';
    seq.push_back(curr);
    int act=curr;
    for(i=act-1;i>=1;i--)
    {
        if(best[i]==best[curr]-1&&pc[(v[i]&v[curr])]==k[curr])
        {
            seq.push_back(i);
            curr=i;
        }
    }
    reverse(seq.begin(),seq.end());
    for(int i=0;i<seq.size();i++)
        cout<<seq[i]<<' ';
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<seq.size();i++)
                 ~^~~~~~~~~~~
subsequence.cpp:34:13: warning: iteration 1028 invokes undefined behavior [-Waggressive-loop-optimizations]
        pc[i]=pc[(i&(i-1))]+1;
        ~~~~~^~~~~~~~~~~~~~~~
subsequence.cpp:33:14: note: within this loop
     for(i=1;i<(1<<20);i++)
             ~^~~~~~~~

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