Submission #550810

#	Time	Username	Problem	Language	Result	Execution time	Memory
550810		Alexandruabcde	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3893 ms	93456 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> PII;
constexpr int NMAX = 1e5 + 5;
constexpr int BMAX = 10;

int N;
int A[NMAX];
int K[NMAX];

PII ans[NMAX];

PII dp[1<<BMAX][1<<BMAX][11];
/*
first - length
second - index
*/

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i <= N; ++ i )
        cin >> A[i];
    for (int i = 1; i <= N; ++ i )
        cin >> K[i];
}

PII Best (PII a, PII b) {
    if (a.first >= b.first) return a;

    return b;
}

void Solve () {
    for (int mask1 = 0; mask1 < (1<<BMAX); ++ mask1 )
        for (int mask2 = 0; mask2 < (1<<BMAX); ++ mask2 ) {
            for (int i = 0; i <= 10; ++ i )
                dp[mask1][mask2][i] = {0, 0};
        }

    for (int i = 1; i <= N; ++ i ) {
        int High = (A[i]>>BMAX);
        int Low = (A[i]&((1<<BMAX) - 1));

        ans[i] = {1, 0};

        for (int mask = 0; mask < (1<<BMAX); ++ mask ) {
            int cnt_bits = __builtin_popcount((High&mask));
            int need = K[i] - cnt_bits;

            if (need < 0 || need > 10) continue;

            ans[i] = Best(ans[i], {dp[mask][Low][need].first + 1, dp[mask][Low][need].second});
        }

        for (int mask = 0; mask < (1<<BMAX); ++ mask ) {
            int cnt_bits = __builtin_popcount((Low&mask));

            if (cnt_bits < 0 || cnt_bits > 10) continue;

            dp[High][mask][cnt_bits] = Best(dp[High][mask][cnt_bits], {ans[i].first, i});
        }
    }

    int ind = 1;
    for (int i = 1; i <= N; ++ i )
        if (Best(ans[i], ans[ind]) == ans[i])
            ind = i;

    vector <int> sol;
    while (ind > 0) {
        sol.push_back(ind);
        ind = ans[ind].second;
    }

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

    cout << sol.size() << '\n';
    for (auto it : sol)
        cout << it << " ";
}

int main()
{
    Read();
    Solve();

    return 0;
}

/*
dp1[mask] = {indice, lungime} maxima pt ultima valoare egala cu mask => Update(O(1)), Query(O(2^20))
dp2[mask][val] = {indice, lungime} maxima pt care ultima valoare contine val biti din mask => Update(O(2^20)), Query(O(1))

Combin dp-urile?
dp[mask1][mask2][aux] = {indice, lungime}, pt care ultima valoare are bitii mask1, in primii 10 biti, si aux biti din mask2 in ultimii 10 biti

A[i] = High * 2^10 + Low
answer pt A[i]
answer = Best(dp[mask][Low][K[i] - CntBits(A[i]&(mask<<10))]) + 1

Update pentru A[i]
dp[High][mask][CntBits(A[i]&mask)] = max(dp[High][mask][CntBits(A[i]&mask)], answer)
*/

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