제출 #1327161

#제출 시각아이디문제언어결과실행 시간메모리
1327161marcus06Longest beautiful sequence (IZhO17_subsequence)C++20
40 / 100
69 ms2096 KiB
#include <bits/stdc++.h>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

using namespace std;
using lli = long long;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n; cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    vector <int> k(n);
    for (int i = 0; i < n; ++i) {
        cin >> k[i];
    }

    int mx = *max_element(a.begin(), a.end());
    vector <int> f(n), trace(n, -1);
    if (mx < (1 << 8)) {
        vector <pair <int, int>> best(1 << 8, {0, -1});
        for (int i = 0; i < n; ++i) {
            int lst = -1;
            f[i] = 1;
            for (int j = 0; j < (1 << 8); ++j) {
                int bits = __builtin_popcount(a[i] & j);
                if (bits == k[i] && best[j].first + 1 > f[i]) {
                    f[i] = best[j].first + 1;
                    trace[i] = best[j].second;
                }
            }
            if (best[a[i]].first < f[i]) {
                best[a[i]] = {f[i], i};
            }
        }
    } else if (n <= 5000) {
        for (int i = 0; i < n; ++i) {
            f[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (__builtin_popcount(a[i] & a[j]) == k[i] && f[j] + 1 > f[i]) {
                    f[i] = f[j] + 1;
                    trace[i] = j;
                }
            }
        }
    }

    int p = max_element(f.begin(), f.end()) - f.begin();
    vector <int> ans;
    for (int i = p; i != -1; i = trace[i]) ans.push_back(i + 1);
    reverse(ans.begin(), ans.end());

    cout << ans.size() << '\n';
    for (auto x: ans) cout << x << ' ';
    return 0;   
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...