Submission #676731

#TimeUsernameProblemLanguageResultExecution timeMemory
676731RandomLBLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
93 ms2952 KiB
#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, best = -1;
    for (int i = 1; i <= n; i++){
        int res = 1;
        for (int mask = 0; mask < 1<<8; mask++){
            if (bits(arr[i]&mask) == tar[i]){
                if (dp[mask]+1 > res){
                    res = dp[mask]+1;
                    pp[i] = pos[mask];
                }
            }
        }
        if (res > dp[arr[i]]){ dp[arr[i]] = res, pos[arr[i]] = i; }
        if (res > best){ mx = i; best = res; }
    }
    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()];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...