Submission #1171281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171281		paulxaxa	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2163 ms	104188 KiB

subsequence

#include <bits/stdc++.h>

#define NMAX 100000
#define LOG 19

#define ll long long int
#define BASE 1024

#define MOD 1000000009


using namespace std;

ifstream fin("cod.in");
ofstream fout("cod.out");

int l[1<<20],r[1<<20];
int bc[1<<10][1<<10];

pair<int,int> dp[1<<10][1<<10][10+1];
int prv[NMAX+1];

int n;

int a[NMAX+1],k[NMAX+1];

int main()
{
    for(int i=0;i<(1<<10);i++)
    {
        for(int j=0;j<(1<<10);j++)
        {
            bc[i][j] = __builtin_popcount(i&j);
        }
    }
    for(int i=0;i<(1<<20);i++)
    {
        l[i] = i >> 10;
        r[i] = i & ((1<<10)-1);
    }

    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin >> k[i];
    }
    int res=0,j=0;
    for(int i=1;i<=n;i++)
    {
        int mx=1;
        for(int lx = 0;lx<(1<<10);lx++)
        {
            int t = k[i] - bc[lx][l[a[i]]];
            if(t >= 0 && t<=10 && dp[lx][r[a[i]]][t].first + 1 > mx )
            {
                mx  = dp[lx][r[a[i]]][t].first + 1;
                prv[i] = dp[lx][r[a[i]]][t].second;
            }
        }
        if(mx > res)
        {
            res = mx;
            j=i;
        }
        for(int rx=0;rx < (1<<10);rx++)
        {
            int t = bc[rx][r[a[i]]];
            if(dp[l[a[i]]][rx][t].first < mx)
            {
                dp[l[a[i]]][rx][t].first = mx;
                dp[l[a[i]]][rx][t].second = i;
            }
        }
    }

    vector<int> path;
    while(j)
    {
        path.push_back(j);
        j = prv[j];
    }
    cout << path.size() << "\n";
    reverse(path.begin(),path.end());
    for(int i : path)
    {
        cout << i << " ";
    }

}

//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