Submission #337938

#	Time	Username	Problem	Language	Result	Execution time	Memory
337938		BY_KUTBILIM	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	896 ms	4588 KiB

subsequence

/** @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+10, 1);
    vector<int> p(n+10, -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)+88];
        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(to < i and 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;
}

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