Submission #506954

#	Time	Username	Problem	Language	Result	Execution time	Memory
506954		syl123456	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6086 ms	1868 KiB

subsequence

#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wparentheses"
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define random random_device rd; mt19937 rng(rd())
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
    if (_split)
        cerr << ", ";
    cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
    cerr << '[';
    for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
    cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << "]\u001b[0m" << endl
#define debuga(i) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name())), cerr << "\u001b[0m"
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    random;
    const int K1 = 2048, K2 = 31;
    uniform_int_distribution<int> dist(1, K2);
    int n;
    cin >> n;
    int a[n], k[n];
    for (int &i : a)
        cin >> i;
    for (int &i : k)
        cin >> i;
    int dp[n], pre[n], ans = 1, last = 0;
    flag :
    for (int i = 0; i < n; ++i) {
        int j = i;
        tie(dp[i], pre[i]) = pi(1, -1);
        auto check = [&](int x) {
            debug(x);
            if (x < 0)
                return false;
            if (__builtin_popcount(a[x] & a[i]) == k[i])
                tie(dp[i], pre[i]) = max(pi(dp[i], pre[i]), pi(dp[x] + 1, x));
            return true;
        };
        for (int _i = 0; _i < K1; ++_i)
            if (!check(--j))
                break;
        while (check(j -= dist(rng)));
        tie(ans, last) = max(pi(ans, last), pi(dp[i], i));
    }
    if (ans >= 5 && ans <= 20)
        goto flag;
    cout << ans << '\n';
    vector<int> v;
    while (~last)
        v.push_back(last + 1), last = pre[last];
    sort(all(v));
    for (int i : v)
        cout << i << ' ';
}

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