Submission #887680

#	Time	Username	Problem	Language	Result	Execution time	Memory
887680		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	1857 ms	96232 KiB

subsequence

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define N 1024
#define M 100100
int en[N][N][11], len[N][N][11], pc[N][N], a[M], k[M], pre[M], n;
int main() {
    for(int i = 1; i < N; i++)
        for(int j = 1; j < N; j++)
            pc[i][j]=__builtin_popcount(i&j);
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        cin >> k[i];
    iota(pre,pre+n+1,0);
    int ans=1,pos=1;
    for(int i = 1; i <= n; i++) {
        int l = a[i]/N, r=a[i]%N, sz = 1;
        for(int j = 0; j < N; j++) {
            int rem = k[i]-pc[l][j];
            if(rem<0||rem>10)
                continue;
            if(sz < len[j][r][rem]+1)
                sz=len[j][r][rem]+1,
                pre[i]=en[j][r][rem];
        }
        if(sz>ans)
            ans=sz,pos=i;
        for(int j = 0; j < N; j++)
            if(len[l][j][pc[r][j]] < sz)
                len[l][j][pc[r][j]]=sz,
                en[l][j][pc[r][j]]=i;
    }
    cout << ans << '\n';
    stack<int> stk;
    while(pos-pre[pos])
        stk.push(pos),
        pos=pre[pos];
    cout << pos;
    while(stk.size()){
        cout << ' ' << stk.top();
        stk.pop();
    }
}

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