Submission #55229

#	Time	Username	Problem	Language	Result	Execution time	Memory
55229		BThero	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	218 ms	16688 KiB

subsequence

// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const bool SEND = 1;

const int MAXN = 1e5+5;

int need[MAXN];

int arr[MAXN];

int par[MAXN];

int dp[MAXN];         

int n;

void calcSlow() {    
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (__builtin_popcount(arr[i] & arr[j]) == need[j]) {
                if (dp[i] + 1 > dp[j]) {
                    dp[j] = dp[i] + 1;
                    par[j] = i;
                }
            }
        }    
    }    
}

void solve() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &need[i]);
    }

    for (int i = 1; i <= n; ++i) {
        dp[i] = 1;
    }

    if (n <= 5000 && SEND) {
        calcSlow();
    }
    else {
        vector<int> M(256, 0);

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 256; ++j) {
                if (__builtin_popcount(arr[i] & j) == need[i]) {
                    if (dp[M[j]] + 1 > dp[i]) {
                        dp[i] = dp[M[j]] + 1;
                        par[i] = M[j];
                    }
                }
            }

            if (dp[i] > dp[M[arr[i]]]) {
                M[arr[i]] = i;
            }
        }
    }

    vector<int> vv;                 
    int mx = 1;

    for (int i = 2; i <= n; ++i) {
        if (dp[i] > dp[mx]) {
            mx = i;
        }
    }

    for (int x = mx; x; x = par[x]) {
        vv.pb(x);
    }

    reverse(all(vv));
    printf("%d\n", vv.size());

    for (int it : vv) {
        printf("%d ", it);
    }
}

int main() {            
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'void solve()':
subsequence.cpp:94:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", vv.size());
                    ~~~~~~~~~^
subsequence.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
subsequence.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
subsequence.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &need[i]);
         ~~~~~^~~~~~~~~~~~~~~~

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