Submission #524081

#TimeUsernameProblemLanguageResultExecution timeMemory
524081NursikLongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
5 ms4428 KiB
#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair

const ll maxn = 1e6 + 100, maxm = 11,  maxk = (1 << 10);
const ll inf = 1000000000, mod = inf + 7, mod2 = 998244353;
const ll pa = 31, block = 400;

using namespace std;

int n;
int a[maxn], k[maxn], len[maxn], last[maxn], dp[maxk][maxk][maxm], cnt[maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i){
        cin >> k[i];
    }
    for (int i = 1; i <= maxn - 1; ++i){
        cnt[i] = __builtin_popcount(i);
    }
    for (int i = 1; i <= n; ++i){
        int f = 0, s = 0;
        for (int j = 0; j < 10; ++j){
            if (1 << j & a[i]){
                f |= (1 << j);
            }
            if ((1 << (j + 10)) & a[i]){
                s |= (1 << j);
            }
        }
        for (int j = 0; j < maxk; ++j){
            int need = k[i] - cnt[j & f];
            if (need >= 0 && need < maxm){
                int pos = dp[j][s][need];
                if (pos != -1 && len[pos] + 1 > len[i]){
                    len[i] = len[pos] + 1;
                    last[i] = pos;
                }
            }
        }
        for (int j = 0; j < maxk; ++j){
            int x = cnt[j & s];
            int ind = dp[f][j][x];
            if (x < maxm && len[ind] < len[i]){
                dp[f][j][x] = i;
            }
        }
    }
    int pos = 0;
    for (int i = 1; i <= n; ++i){
        if (len[pos] < len[i]){
            pos = i;
        }
    }
    vector<int> v;
    while (pos > 0){
        v.pb(pos);
        pos = last[pos];
    }
    cout << v.size() << '\n';
    reverse(v.begin(), v.end());
    for (auto it : v){
        cout << it << " ";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...