Submission #89990

#	Time	Username	Problem	Language	Result	Execution time	Memory
89990		Bodo171	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4706 ms	219768 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);
const int zr=20;
vector<int> seq;
int dp[valmax][42];
int v[nmax],k[nmax],best[nmax];
int pc[(1<<20)+5];
int n,i,j,ans,curr;
void ins(int x,int val)
{
    for(int i=0;i<lim;i++)
        dp[(x^i)][pc[i]-pc[x]+zr]=max(dp[(x^i)][pc[i]-pc[x]+zr],val);
}
int gt(int x,int b,int btot)
{
    int ret=0;
    for(int i=0;i<lim;i++)
            if(btot-pc[i]-2*b+zr>=0&&btot-pc[i]-2*b+zr<=40)
               ret=max(ret,dp[(x^(i<<10))][btot-pc[i]-2*b+zr]);
    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++)
                 ~^~~~~~~~~~~

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