Submission #92728

#	Time	Username	Problem	Language	Result	Execution time	Memory
92728		toloraia	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	70 ms	12408 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n;
int a[N], b[N];
int dp[N], w[N];
int B[N * 20];
int D[N * 10], d[N * 10];
vector < int > V;

int main()
{
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    for (int i = 1; i <= n; i++)
        cin>>b[i];
    B[0] = 0;
    for (int i = 1; i < (1<<20); i++)
        B[i] = 1 + B[(i & (i - 1))];
    dp[1] = 1;
    D[a[1]] = 1;
    for (int i = 2; i <= n; i++){
        if (n <= 5000){
            for (int j = 1; j < i; j++)
                if (B[(a[i] & a[j])] == b[i])
                    if (dp[i] < dp[j]){
                        dp[i] = dp[j];
                        w[i] = j;
                    }
        }
        else {
            for (int j = 0; j < (1<<8); j++)
                if (B[a[i] & j] == b[i])
                    if (dp[i] < D[j]){
                        dp[i] = D[j];
                        w[i] = d[j];
                    }
        }
        dp[i]++;
        if (D[a[i]] < dp[i]){
            D[a[i]] = dp[i];
            d[a[i]] = i;
        }
    }
    int x = 1;
    for (int i = 2; i <= n; i++)
        if (dp[i] > dp[x])
            x = i;
    cout<<dp[x]<<endl;
    while (x){
        V.push_back(x);
        x = w[x];
    }
    for (int i = (int)V.size() - 1; i >= 0; i--)
        cout<<V[i]<<" ";
    cout<<endl;
    return 0;
}

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