Submission #1127649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127649		mirciu	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	596 ms	327680 KiB

subsequence

#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 1e5 + 9;
const int BMAX = 10;
const int MMAX = 1 << BMAX;

int n, a[NMAX], k[NMAX], len[NMAX], f[NMAX];

int dp[MMAX + 1][MMAX + 1][BMAX + 1];
int t[MMAX + 1][MMAX + 1][BMAX + 1];

inline int get_left(const int x)
{
    return x >> 10;
}

inline int get_right(const int x)
{
    return x & ((1 << 10) - 1);
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> k[i];

    for (int i = 1; i <= n; ++i)
    {
        len[i] = 1;
        f[i] = 0;

        int l = get_left(a[i]), r = get_right(a[i]);

        for (int left_mask = 0; left_mask < (1 << 10); ++left_mask)
        {
            int bit_count = __builtin_popcount(l & left_mask);
            if (k[i] >= bit_count &&
                k[i] - bit_count <= 10)
            {
                int crt_len = dp[left_mask][r][k[i] - bit_count] + 1;
                if (crt_len > len[i])
                {
                    len[i] = crt_len;
                    f[i] = t[left_mask][r][k[i] - bit_count];
                }
            }
        }
        for (int right_mask = 0; right_mask < (1 << 10); ++right_mask)
        {
            int bit_count = __builtin_popcount(r & right_mask);
            if (dp[l][right_mask][bit_count] < len[i])
            {
                dp[l][right_mask][bit_count] = len[i];
                t[l][right_mask][bit_count] = i;
            }
        }
    }

    int bst = 1;
    for (int i = 2; i <= n; ++i)
        if (len[i] > len[bst])
            bst = i;

    cout << len[bst] << '\n';
    vector<int> res;
    for (int x = bst; x; x = f[x])
        res.push_back(x);

    reverse(res.begin(), res.end());

    for (auto e : res)
        cout << e << ' ';

    cout << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--)
        solve();
    return 0;
}

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