Submission #848482

#	Time	Username	Problem	Language	Result	Execution time	Memory
848482		yifei04	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6042 ms	55496 KiB

subsequence

#include <iostream>
#include <vector>
#include <numeric>
#include <functional>
#include <bitset>
#include <algorithm>
#include <stdio.h>
#include <unordered_set>
#include <assert.h>  
#include <unordered_map>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <random>
#include <chrono>
#include <string>


#pragma GCC target("avx2")
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
#define all(x) x.begin(), x.end()
#define read(x) for (auto &i : x) cin >> i;
#define sz(x) (int) (x).size()
#define len(x) (int) (x).length()

constexpr int INF = 1e9 + 9;
constexpr long long INF_LL = 1e18 + 9;
constexpr int MOD = 998244353;

// up, right, down, left
constexpr int mX_4 [] = {0, 1, 0, -1};
constexpr int mY_4 [] = {-1, 0, 1, 0};

using namespace std;

// random number
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

ll rand_num(ll l, ll r) {
    return rng() % (r - l) + l;
}

template <typename T, typename S>
ostream& operator<<(ostream& _os, const pair<T, S>& p) {
    _os << p.first << ' ' << p.second;
    return _os;
}

template <typename T>
void dbg_vec(string str, vector <T> &x) {
    cerr << "DBG " << str << '\n';
    for (int i = 0; i < sz(x); ++i) {
        cerr << "I " << i << " -> " << x[i] << '\n';
    }
    cerr << '\n';
}

const int MAX_BIT_DBG = 3;
void dbg_bits(int n) {
    bitset <MAX_BIT_DBG> v (n);
    cerr << v << '\n';
}

template <typename T>
bool vmin(T &a, T b) { return (a > b ? a = b, true : false); }
 
template <typename T>
bool vmax(T &a, T b) { return (a < b ? a = b, true : false); }  



void solve() {
    int n; cin >> n;
    vector <int> a (n); read(a);
    vector <int> k (n); read(k);

    vector <vector <int> > pos (1 << (21));


    for (int i = 0; i < n; ++i) {
        pos[a[i]].push_back(i);
    }

    vector <int> dp (n);
    vector <int> rec (n, -1);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int v = a[i] & a[j];
            if (__builtin_popcount(v) == k[i]) {
                if (vmax(dp[i], dp[j] + 1)) {
                    rec[i] = j;
                }
            }
        }
    }

    int idx = max_element(all(dp)) - dp.begin();

    vector <int> ans = {idx + 1};

    while (rec[idx] != -1) {
        idx = rec[idx];
        ans.push_back(idx + 1);
    }

    cout << sz(ans) << '\n';
    reverse(all(ans));
    for (int x : ans) cout << x << " ";
    cout << '\n';
}


signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tt = 1; // cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

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