Submission #55390

#	Time	Username	Problem	Language	Result	Execution time	Memory
55390		BThero	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3767 ms	85920 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 int MAXN = 1e5+5;

const int M = 1024;

int d[11][M][M];

int need[MAXN];

int arr[MAXN];

int par[MAXN];

int dp[MAXN];

int bp[M];

int n;

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 = 0; i < M; ++i) {
        bp[i] = __builtin_popcount(i);
    }

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

        int lc = (arr[i] >> 10), rc = arr[i] - (lc << 10);

        for (int lp = 0; lp < M; ++lp) {
            int k = need[i] - bp[lc & lp];

            if (k < 0 || k > 10) {
                continue;
            }

            int id = d[k][lp][rc];

            if (dp[id] + 1 > dp[i]) {
                dp[i] = dp[id] + 1;
                par[i] = id;
            }
        }

        for (int rn = 0; rn < M; ++rn) {
            int k = bp[rc & rn];

            int &id = d[k][lc][rn];

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

    int mx = 1;

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

    vector<int> vv;

    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:95: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:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
subsequence.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
subsequence.cpp:42: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: 60 / 60