Submission #164572

#	Time	Username	Problem	Language	Result	Execution time	Memory
164572		qwerty234	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5683 ms	176992 KiB

subsequence

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define f first
#define se second
#define pb push_back
 
 
using namespace std;
 
 
const int N = 1e5 + 219;
const ll M = 3e5 + 19;
const ll inf = 1e15 + 10;
const ll mod = 1e9 + 7;


int n, a[N], k[N], F[1030];
pair<int, int> mx[1030][1030][21], dp[N];
vector <int> b;


void go(int u) {
    if (dp[u].f == 1) {
        b.pb(u);
        return;
    }
    go(dp[u].se);
    b.pb(u);
}


int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &k[i]);
    for (int i = 0; i < 1024; i++)
        F[i] = __builtin_popcount(i);
    for (int i = 1; i <= n; i++) {
        int Lm, Rm, tmp;
        Lm = (a[i]>>10);
        Rm = (a[i] & 1023);
        for (int mask = 0; mask < 1024; mask++) {
            tmp = k[i] - F[Lm & mask];
            if (tmp < 0)
                continue;
            dp[i] = max(dp[i], {1 + mx[mask][Rm][tmp].f, mx[mask][Rm][tmp].se});
        }
        for (int mask = 0; mask < 1024; mask++) {
            int tmp = F[Rm & mask];
            mx[Lm][mask][tmp] = max(mx[Lm][mask][tmp], {dp[i].f, i});
        }
    }
    int ans = 0, id;
    for (int i = 1; i <= n; i++)
        if (dp[i].f > ans) {
            ans = dp[i].f;
            id = i;
        }
    go(id);
    printf("%d\n", b.size());
    for (int i = 0; i < b.size(); i++)
        printf("%d ", b[i]);
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:64:28: 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", b.size());
                    ~~~~~~~~^
subsequence.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b.size(); i++)
                     ~~^~~~~~~~~~
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:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
subsequence.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k[i]);
         ~~~~~^~~~~~~~~~~~~
subsequence.cpp:63:7: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
     go(id);
     ~~^~~~

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