제출 #337934

#제출 시각아이디문제언어결과실행 시간메모리
337934BY_KUTBILIMLongest beautiful sequence (IZhO17_subsequence)C++14
23 / 100
1435 ms262144 KiB
/** @BY_KUTBILIM **/
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).end()

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

    int n;
    cin >> n;
    int a[n], k[n];
    for(int i = 0; i < n; i++)cin >> a[i];
    for(int i = 0; i < n; i++)cin >> k[i];
    
    vector<int> dp(n, 1);
    vector<int> p(n, -1);
    if(n <= 5000){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(__builtin_popcount(a[i] & a[j]) == k[i]){
                    if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        p[i] = j;
                    }
                }
            }
        }
    } else{
        vector<int> index[(1 << 8)];
        for(int i = 0; i < n; i++){
            index[a[i]].pb(i);
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < (1 << 8); j++){
                if(__builtin_popcount(a[i] & j) == k[i]){
                    for(auto to : index[j]){
                        if(dp[i] < dp[to] + 1){
                            dp[i] = dp[to] + 1;
                            p[i] = to;
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    int I = 0;
    for(int i = 0; i < n; i++){
        if(dp[i] > ans){
            ans = dp[i];
            I = i;
        }
    }
    vector<int> path;
    while(I != -1){
        path.pb(I + 1);
        I = p[I];
    }
    cout << ans << endl;
    reverse(all(path));
    for(auto v : path){
        cout << v << " ";
    }
      
    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...