제출 #1102696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102696		Vectors_Master	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	929 ms	128840 KiB

subsequence

#include<bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define LL long long
#define LD long double
#define pb push_back
#define F first
#define S second

const double PI=acos(-1);
const int KL=1e6+10;
const LL MOD=1e9+7;

using namespace std;

struct SOS_Bag {
    int left,right;
    vector<vector<vector<pair<int,int>>>> sos;
    vector<int> pop_count;
    SOS_Bag(int k) {
        left=k/2,right=k-left;
        sos=vector((1<<left),vector((1<<right),vector(right+1,make_pair(0,-1))));
        pop_count=vector((1<<right),0);
        for(int i=1;i<(1<<right);i++) {
            pop_count[i]=pop_count[i/2]+i%2;
        }
    }
    void update(int mask,int val) {
        int l_part=(mask&((1<<left)-1));
        int r_part=(mask>>left);
        for(int r_mask=0;r_mask<(1<<right);r_mask++) {
            int bits=pop_count[r_mask&r_part];
            sos[l_part][r_mask][bits]=max(sos[l_part][r_mask][bits],make_pair(val,mask));
        }
    }
    pair<int,int> query(int intersection,int mask) {
        int l_part=(mask&((1<<left)-1));
        int r_part=(mask>>left);
        auto opt=make_pair(0,-1);
        for(int l_mask=0;l_mask<(1<<left);l_mask++) {
            int d=pop_count[l_mask&l_part];
            if(d>intersection)continue;
            d=intersection-d;
            if(d>right)continue;
            opt=max(opt,sos[l_mask][r_part][d]);
        }
        return opt;
    }
};

void solveTS() {
    int n;
    cin>>n;
    vector<int> a(n),k(n);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>k[i];



    SOS_Bag bag(20);
    vector<int> pr(n,-1),occ((1<<20),-1);
    auto opt=make_pair(0,0);
    for(int i=0;i<n;i++) {
        auto ret=bag.query(k[i],a[i]);
        ret.F++;
        if(ret.S!=-1)pr[i]=occ[ret.S];
        opt=max(opt,make_pair(ret.F,i));
        occ[a[i]]=i;
        bag.update(a[i],ret.F);

    }
    vector<int> vec;
    int node=opt.S;

    while(node!=-1) {
        vec.pb(node);
        node=pr[node];
    }
    reverse(all(vec));
    cout<<(int)vec.size()<<"\n";
    for(auto v:vec) {
        cout<<v+1<<" ";
    }cout<<"\n";



}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int TS=1;
    // cin>>TS;
    while (TS--) {
        solveTS();
    }
    return 0;
}

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