제출 #676728

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

subsequence

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define siz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define bits(x) __builtin_popcount(x)
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values){
    cout << vars << " = ";
    string delim = "";
    (...,(cout << delim << values, delim = ", "));
    cout << endl;
}
//===========================================
const int MAX = 1e5+5;
int arr[MAX], tar[MAX], dp[MAX], pos[MAX], pp[MAX];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1; i <= n; i++) cin >> tar[i];
    if (n <= 5000){
        int mx = 0;
        for (int i = 1; i <= n; i++){
            dp[i] = 1;
            for (int j = 1; j < i; j++){
                if (bits(arr[i]&arr[j]) == tar[i] && dp[j]+1 > dp[i]){
                    dp[i] = dp[j]+1;
                    pp[i] = j;
                }
            }
            if (dp[i] > dp[mx]) mx = i;
        }
        vector<int> v; while (mx){ v.pb(mx); mx = pp[mx]; }
        cout << siz(v) << "\n";
        reverse(all(v)); for (int x: v) cout << x << " \n"[x==v.back()];
        return 0;
    }
    int mx = 0;
    for (int i = 1; i <= n; i++){
        for (int mask = 0; mask < 1<<8; mask++){
            if (bits(arr[i]&mask) == tar[i]){
                if (dp[mask]+1 > dp[arr[i]]){
                    dp[arr[i]] = dp[mask]+1;
                    pp[i] = pos[mask];
                }
            }
        }
        dp[arr[i]] = max(dp[arr[i]], 1);
        pos[arr[i]] = i;
        if (dp[arr[i]] >= dp[arr[mx]]) mx = i;
    }
    vector<int> v; while (mx){ v.pb(mx); mx = pp[mx]; }
    cout << siz(v) << "\n";
    reverse(all(v)); for (int x: v) cout << x << " \n"[x==v.back()];
}

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