Submission #1140162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140162		ByeWorld	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3343 ms	257480 KiB

subsequence

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+50;
const int SQRT = 610;
const int MAXA = 50;
const int MOD = 998244353;
const int LOG = 21;
const int INF = 1e16+100;
const int INF2 = 1e18;
const ld EPS = 1e-12;
const int bit = 10;

struct DP {
    int len, ba;
} dp[(1<<bit)][(1<<bit)][bit+5];
int n, a[MAXN], b[MAXN], prv[MAXN];
int dif[(1<<bit)][(1<<bit)];

signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=0; i<(1<<bit); i++)
        for(int j=0; j<(1<<bit); j++)
            dif[i][j] = __builtin_popcount(i & j);

    cin>>n;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) cin >> b[i];

    int idx = 0, tot = 0;
    for(int i=1; i<=n; i++){
        int l = (a[i]>>bit), r = a[i] % (1<<bit);
        int best = 1;
        for(int j=0; j<(1<<bit); j++){
            int need = b[i] - dif[j][l];
            if(need < 0 || need > bit) continue;

            if(dp[j][r][need].len + 1 > best){
                best = dp[j][r][need].len + 1;
                prv[i] = dp[j][r][need].ba;
            }
        }

        if(best > tot){
            tot = best; idx = i;
        }

        for(int j=0; j<(1<<bit); j++){
            DP &new_state = dp[l][j][dif[r][j]];
            if(new_state.len < best){
                new_state.len = best;
                new_state.ba = i;
            }
        }
    }

    vector <int> ret;
    int nw = idx;
    while(nw != 0){
        ret.pb(nw); nw = prv[nw];
    }
    reverse(ret.begin(), ret.end());
    cout << tot << '\n';
    for(auto in : ret) cout << in<<' ';
    cout << '\n';
}

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