Submission #936356

#	Time	Username	Problem	Language	Result	Execution time	Memory
936356		atom	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	2405 ms	262144 KiB

subsequence

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif


const int M1 = 8;
const int M2 = 10;
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int n; cin >> n;
    vector <int> a(n + 5), k(n + 5);

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

    // subtask 1-2:
    vector <int> opt(n + 5, -1);
    int p = 0, ans = 0;
    
    if (n <= 5000) {
        vector <int> dp(n + 5, 1);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                int cur = (__builtin_popcount(a[i] & a[j]) == k[i])? dp[j] : 0;
                if (dp[i] < cur + 1) {
                    opt[i] = j;
                    dp[i] = cur + 1;
                }
            }
            if (ans < dp[i]) {
                p = i;
                ans = dp[i];
            } 
        }   
    }
    else if (*max_element(a.begin(), a.end()) < (1 << M1)) {
        vector <pair <int, int>> dp(1 << M1), nxt_dp(1 << M1);
        vector <int> f(n + 5, 1);    
        
        for (int i = 1; i <= n; ++i) {
            nxt_dp[a[i]].first = max(nxt_dp[a[i]].first, 1);

            for (int msk = 0; msk < (1 << M1); ++msk) {
                int cnt = __builtin_popcount(a[i] & msk);
                if (cnt == k[i] && nxt_dp[a[i]].first < dp[msk].first + 1) {
                    nxt_dp[a[i]].first = dp[msk].first + 1;
                    opt[i] = dp[msk].second;
                }
            }

            for (int msk = 0; msk < (1 << M1); ++msk) {
                if (dp[msk].first != nxt_dp[msk].first)
                    nxt_dp[msk].second = i;
                f[i] = max(f[i], nxt_dp[msk].first);
            }
            dp = nxt_dp;
            // debug(dp);
        }   

        for (int i = 1; i <= n; ++i) {
            if (ans < f[i]) {
                ans = f[i];
                p = i;
            }
        }  
    }
    else { // subtask 4: split a(i) to 2 parts: first 10 bits - prf and last 10 bits - suf
        // a(i) = (prf | suf) & msk = (msk & prf) | (msk & suf) = x(i);
        // dp(l, r, k) at i: 
        // l(x) is prf of x, r(x) is suf of x, fixed l = l(x), bit(r(x), r) = k
        vector <vector <vector <pair<int, int>>>> 
            dp((1 << M2) + 5, vector <vector <pair<int, int>>> ((1 << M2) + 5, vector <pair<int, int>> (M2 + 5)));
        vector <int> f(n + 5);
        vector <vector <int>> b((1 << M2) + 5, vector <int> ((1 << M2) + 5));

        for (int x = 0; x < (1 << M2); ++x) 
            for (int y = 0; y < (1 << M2); ++y) 
                b[x][y] = __builtin_popcount(x & y);

        for (int i = 1; i <= n; ++i) {
            int prf = 0, suf = 0;    
            for (int j = 0; j < M2; ++j) 
                prf |= (a[i] & (1 << j))? (1 << j) : 0;
            for (int j = M2; j < M2 * 2; ++j) 
                suf |= (a[i] & (1 << j))? (1 << (2 * M2 - j)) : 0;

            f[i] = max(f[i], 1);
            // for any x such bit(x, a(i)) = k(i) -> bit(prf(x), prf(a(i))) + bit(suf(x), suf(a(i))) = k(i)
            // -> fixed prf(x), suf(x) can be found by the following 
            for (int msk = 0; msk < (1 << M2); ++msk) {
                // transition: for each fixed msk find which state contributed to current answer: dp(msk, )
                // required value of bit(suf(x), suf(a(i))) 
                int needed = k[i] - b[msk][prf];
                if (0 <= needed && needed < M2 && f[i] < dp[msk][suf][needed].first + 1) {
                    f[i] = dp[msk][suf][needed].first + 1;
                    opt[i] = dp[msk][suf][needed].second;
                }
            }
            // Update which states affected by a[i]
            // dp(l, r, k): l is fixed prf, k is bit(r, suf(a[i])) ->...
            for (int msk = 0; msk < (1 << M2); ++msk) {
                int cnt = b[msk][suf];
                if (dp[prf][msk][cnt].first < f[i])
                    dp[prf][msk][cnt] = make_pair(f[i], i);
            }
        }

        for (int i = 1; i <= n; ++i) {
            if (ans < f[i]) {
                ans = f[i];
                p = i;
            }
        }
    }
    
    // debug(opt);
    vector <int> ids;
    while (p != -1) {
        ids.push_back(p);
        p = opt[p];
    }
    reverse(ids.begin(), ids.end());
    cout << ans << "\n";
    for (int x : ids) cout << x << " ";
    cout << "\n"; 
}

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