Submission #1101663

#TimeUsernameProblemLanguageResultExecution timeMemory
1101663orcslopLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
1 ms504 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt")
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 1e5 + 5; 

int n; 
int a[N]; 
int k[N]; 
int p[N]; 
int dp[N]; 

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n; 
    for(int i = 1; i <= n; i++){
        cin >> a[i]; 
    }
    for(int i = 1; i <= n; i++){
        cin >> k[i]; 
    }
    fill(dp, dp + n + 1, 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(ckmax(dp[i], dp[j] + 1)){
                    p[i] = j; 
                }
            }
        }
    }
    int ans = 0, curr = 0; 
    for(int i = 1; i <= n; i++){
        if(ckmax(ans, dp[i])){
            curr = i; 
        }
    }
    vector<int> ret; 
    while(curr){
        if(!ret.empty() && ret.back() == curr) break; 
        ret.push_back(curr); 
        curr = p[curr]; 
    }
    cout << ans << '\n'; 
    reverse(ret.begin(), ret.end()); 
    for(auto x : ret) 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...