제출 #1122554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122554		asli_bg	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	0 ms	328 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sp <<' '<<
#define pb push_back

#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(a) for(auto el:a) cout<<el<<' '; cout<<endl;
#define contp(a) for(auto el:a) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

#define DEBUG(x) cout<<#x sp ":" sp x<<endl;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef long long ll;

#define mid (l+r)/2

#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
#define carp(x,y) ((x%MOD)*(y%+MOD))%MOD

const int MAXK=300;
const int MAXN=1e5+5;

int n;
vi a,k;

int dp[MAXK];
//dp[i]-->{i.sayıyla biten max lengthli array ve bir önceki eleman}
int pre[MAXN];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    a.resize(n+1);
    k.resize(n+1);

    int mx=0;
    FORE(i,1,n+1){
        cin>>a[i];
        mx=max(mx,a[i]);
    }
    FORE(i,1,n+1) cin>>k[i];

    if(mx<300){ //3.subtask
        pii cev={1,1};

        vi used(300,-1);
        used[0]=0;
        
        FORE(i,1,n+1){

            if(dp[a[i]]==0){
                dp[a[i]]=1;
                pre[i]=0;
            }

            FOR(j,256){
                if(used[j]==-1) continue;
                if(__builtin_popcount(j&a[i])!=k[i]) continue;

                //cout<<"here" sp j sp a[i] sp k[i]<<endl;

                if(dp[j]+1>dp[a[i]]){
                    dp[a[i]]=dp[j]+1;
                    pre[i]=used[j];
                }
            }

            if(dp[a[i]]>cev.fi){
                cev.fi=dp[a[i]];
                cev.se=i;
            }

            if(used[a[i]]==-1) used[a[i]]=i;
        }

        //DEBUG(cev.fi);
        //DEBUG(cev.se);

        cout<<cev.fi<<endl;
        vi route;
        while(cev.se!=0){
            route.pb(cev.se);
            cev.se=pre[cev.se];
        }

        reverse(all(route));

        assert(!route.empty());
        cont(route);
    }
    /*else{ //1 ve 2. subtask

    }*/
}       

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