Submission #1134991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134991		sitingfake	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	2101 ms	96020 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define ll long long
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) ((x>>(i))&1)
#define off(x,i) (x^(1<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
const int mod=1e9+7;
const long long linf=1e18+3;
const int inf=1e9;
const int maxarr=1e6+5;
const double pi=acos(-1);
const int dx[]={0,1,-1,0};
const int dy[]={1,0,0,-1};
const int maxn=2e5+7;
int n;
int a[maxn],k[maxn];
namespace sub2
{
    int dp[maxn];
    ii ans;
    void trace(int i)
    {
        if(dp[i]==1)
        {
            cout<<i<<" ";
            return;
        }
        else
        {
            for(int j=i-1;j>=1;j--)
            {
                int val=a[i]&a[j];
                if(__builtin_popcount(val)==k[i]&&dp[j]==dp[i]-1)
                {
                    trace(j);
                    cout<<i<<" ";
                    break;
                }
            }
        }
    }
    void solve()
    {
        for(int i=1;i<=n;i++)
        {
            dp[i]=1;
            for(int j=i-1;j>=1;j--)
            {
                int val=a[i]&a[j];
                if(__builtin_popcount(val)==k[i])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            if(dp[i]>ans.fi)
            {
                ans.fi=dp[i];
                ans.se=i;
            }
        }
        cout<<ans.fi<<"\n";
        trace(ans.se);
    }
}
namespace full
{
    int pre[maxn];
    ii ans;
    const int B=10;
    ii dp[1<<B][1<<B][B+1];
    int bc[1<<B][1<<B];
    void init()
    {
        for(int i=0;i<(1<<B);i++)
        {
            for(int j=0;j<(1<<B);j++)
            {
                bc[i][j]=__builtin_popcount(i&j);
            }
        }
    }
    void solve()
    {
        init();
        for(int i=1;i<=n;i++)
        {
            int len=1;
            int l=a[i]>>B;
            int r=a[i]&((1<<B)-1);
            for(int mask=0;mask<(1<<B);mask++)
            {
                int need=k[i]-bc[mask][l];
                if(need<0||need>B) continue;
                if(dp[mask][r][need].fi+1>len)
                {
                    len=dp[mask][r][need].fi+1;
                    pre[i]=dp[mask][r][need].se;
                }
            }
            for(int mask=0;mask<(1<<B);mask++)
            {
                if(dp[l][mask][bc[mask][r]].fi<len)
                {
                    dp[l][mask][bc[mask][r]]=ii(len,i);
                }
            }
            if(ans.fi<len)
            {
                ans.fi=len;
                ans.se=i;
            }
        }
        cout<<ans.fi<<"\n";
        int i=ans.se;
        vector<int>res;
        while(pre[i]!=0)
        {
            res.push_back(i);
            i=pre[i];
        }
        res.push_back(i);
        reverse(all(res));
        for(int x:res) cout<<x<<" ";
    }
}
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i];
   for(int i=1;i<=n;i++) cin>>k[i];
   full::solve();
   //execute;
}
/*
5
5 3 5 3 5
10 1 20 1 20
*/

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