Submission #1265386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265386		herreinstein	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	0 ms	320 KiB

subsequence

#include <bits/stdc++.h>
#define int long long int
#define ff first
#define ss second
const int MOD = 998244353;
const int N = 2e5 + 5;
using namespace std;
int a[N], b[N];
pair<int, int> dp[N];
void solve(){
    int n;
    cin >> n;
    dp[0] = {0, -1};
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        dp[i] = {1, 0};
    }
    for(int i = 1; i <= n; i++){
        cin >> b[i];
    }
    if(n <= 5005){
        for(int i = 2; i <= n; i++){
            for(int j = 1; j < i; j++){
                if(__builtin_popcount(a[i] & a[j]) == b[i]) {
                    if(dp[i].ff < dp[j].ff + 1){
                        dp[i] = {dp[j].ff+1, j};
                    }
                }
            }
        }
    }
    else{
        pair<int, int> mx[256];
        for(int i = 0; i < 256; i++) mx[i] = {0, 0};
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < 256; j++){
                if(__builtin_popcount(a[i] & j) == b[i]){
                    if(dp[i].ff < mx[j].ff + 1){
                        dp[i] = {mx[j].ff+1, mx[j].ss};
                    }
                }
            }
            if(mx[a[i]].ff < dp[i].ff){
                mx[a[i]] = {dp[i].ff, i};
            }
        }
    }
    int mx = 0, k;
    for(int i = 1; i <= n; i++){
        if(dp[i].ff > mx) mx = dp[i].ff, k = i;
    }
    cout << dp[k].ff << endl;
    vector<int> pth;
    while(dp[k].ss != -1){
        pth.push_back(k);
        k = dp[k].ss;
    }
    for(int i = pth.size()-1; i > -1; i--) cout << pth[i] << " ";
    cout << endl; 
}
int32_t main(){
    
    int t;
    cin >> t;
    // t = 1;
    while(t--) solve();
}

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