Submission #676723

#	Time	Username	Problem	Language	Result	Execution time	Memory
676723		RandomLB	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	46 ms	1668 KiB

subsequence

#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], 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;
    }
}

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