제출 #765749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765749		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	54 ms	1800 KiB

subsequence

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using pii = pair<int, int>;
const int B = 8;
const int maxn = 100005;
int a[maxn], k[maxn];
int dp[maxn], pre[maxn];
int n;
void sub12() {
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> k[i];
    for (int i = 1; i <= n; i++) dp[i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (__builtin_popcount(a[i] & a[j]) == k[i]) {
                if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    pre[i] = j;
                }
            }
        }
    }
    int mx = 0, pos = 0;
    for (int i = 1; i <= n; i++) {
        if (dp[i] > mx) {
            mx = dp[i];
            pos = i;
        }
    }
    cout << mx << endl;
    stack<int> s;
    while (pos) {
        s.push(pos);
        pos = pre[pos];
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}
namespace subtask3 {
    struct State {
        int len, end;
    };
    void solve() {
        vector<vector<int>> bc(1 << B, vector<int>(1 << B));
        for (int i = 0; i < (1 << B); i++) {
            for (int j = 0; j < (1 << B); j++) {
                bc[i][j] = __builtin_popcount(i & j);
            }
        }
        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 ans = 1;
        int best_i = 0;
        vector<int> prv(n);               
        iota(prv.begin(), prv.end(), 0); 
        vector<State> dp1(1 << B, State{-1, -1});
        for (int i = 0; i < n; i++) {
            if (dp1[a[i]].len == -1) {
                dp1[a[i]].len = 1;
                dp1[a[i]].end = i;
            }
            for (int j = 0; j < (1 << B); j++) {
                if (bc[j][a[i]] == k[i] && dp1[j].len + 1 > dp1[a[i]].len) {
                    dp1[a[i]].len = dp1[j].len + 1;
                    dp1[a[i]].end = i;
                    prv[i] = dp1[j].end;
                }
            }
            if (dp1[a[i]].len > ans) {
                ans = dp1[a[i]].len;
                best_i = i;
            }
        }
        cout << ans << endl;
        vector<int> res;
        while (prv[best_i] != best_i) {
            res.push_back(best_i);
            best_i = prv[best_i];
        }
        res.push_back(best_i);
        reverse(res.begin(), res.end());
        for (int x : res) { cout << x + 1 << " "; }
    }
};
int main() {
    cin >> n;
    if (n <= 5000) {
        sub12();
    } else {
        subtask3::solve();
    }
    return 0;
}

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