Submission #503030

#	Time	Username	Problem	Language	Result	Execution time	Memory
503030		sberens	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3236 ms	93392 KiB

subsequence

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)


using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

template<typename T>
using oset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

//const ll M = 1000000007;
//const ll infll = M * M;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vi a(n), k(n);
    F0R(i, n) cin >> a[i];
    F0R(i, n) cin >> k[i];
    int B = 10;
    vi c(1 << B);
    F0R(i, 1 << B) c[i] = __builtin_popcount(i);
    // the dp for subtask 3 is dp[x] = length of lbs ending with x
    // dp[a[i]] = min(dp[x]), x & a[i] == k[i]
    // however this is O(n * max(a))
    // another dp is
    // let dp[x][k] be the index of the lbs s.t. a[dp[x][k]] & x == k
    // l[i] = dp[a[i]][k[i]] + 1
    // if (a[i] & x == K) smin(dp[x][K], l[i]) (for all x, K)
    // also O(n * max(a))
    // but we can combine the two approaches
    vi l(n, 1);
    // let l[i] be the length of the lbs ending at i
    vv<vi> dp(1 << B, vvi(1 << B, vi(B + 1, -1)));
    // let dp[p][s][K] be the index of the lbs s.t. the last element of the lbs
    // has the first B bits equal to p, and the remaining B bits (call them r)
    // are such that r & s == K
    // let's iterate over the high bits (p) (we are processing element at index i),
    //
    // now iterate over the low bits (s)
    // dp[hi(a[i])][s][
    int S = (1 << B) - 1;
    vi rec(n, -1);
    F0R(i, n) {
        int p = a[i] >> B;
        int s = a[i] & S;
        // in this loop we want to update l[i], so we are looking at
        // past values of the dp and "joining" them with a[i]
        F0R(m, 1 << B) {
            int K = k[i] - c[p & m]; // we already get c[p&m] bits from the prefix
            if (!(0 <= K && K <= B)) continue; // this prefix is invalid
            int j = dp[m][s][K];
            if (j == -1) continue;
            if (l[i] < l[j] + 1) {
                l[i] = l[j] + 1;
                rec[i] = j;
            }
        }

        F0R(m, 1 << B) {
            int &j =dp[p][m][c[s & m]];
            if (j == -1 || l[j] < l[i]) {
                j = i;
            }
        }
    }
    int end = max_element(all(l)) - l.begin();
    cout << l[end] << '\n';
    vi res;
    for (; end != -1; end = rec[end]) res.pb(end);
    R0F(i, res.size()) cout << res[i] + 1 << ' ';
}

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