제출 #211298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211298		vinhhung053	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	5 ms	384 KiB

subsequence

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORE(it,v) for(__typeof((v).begin() it=(v).begin();it!=(v).end();i++)
#define IN(v) cerr<<v<<endl
#define SET(a,x) memset((a),(x),sizeof(a))
#define mod 1000000000

#define fi first
#define se second
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> iii;
typedef pair<ll,int> lii;

template <typename T> inline void read(T &x)
{
    int am=0;char k;
    while(!(isdigit(k=getchar()))&&k!='-');
    if (k=='-') k=getchar(),am=1;
    x=k-48;
    while(isdigit(k=getchar())) x=x*10+k-48;
    if (am) x=-x;
}

template <typename T> inline void writep(T x)
{
    if (x>=10) writep(x/10);
    putchar(x%10+48);

}
template <typename T> inline void write(T x)
{
    if(x<0) putchar ('-'),x=-x;
    writep(x);
}
template <typename T> inline void writeln(T x)
{
    write(x);
    putchar('\n');
}

template <typename T> inline void writesp(T x)
{
    write(x);
    putchar(' ');
}

const int N=1000005;

int n, a[N], k[N], f[N],trace[N];
ii bit[10004];
int bitcount(int so)
{
    int dem=0;
    while(so) dem+=so%2,so=so/2;
    return dem;
}

void Solve()
{
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    FOR(i,1,n) cin >> k[i];
    int mx=1,vt=1;
    FOR(i,1,n) f[i]=1;
    FOR(i,2,n)
        FOR(j,1,i-1) if (bitcount(a[i]&a[j])==k[i])
        if(f[i]<f[j]+1)
        {
            f[i]=f[j]+1;
            trace[i]=j;
            if(mx<f[i]) mx=f[i],vt=i;
        }
    cout << mx <<endl;
    deque<int> g;
    while(mx) g.push_front(vt),mx--,vt=trace[vt];
    FOR(i,0,(int)g.size()-1) cout << g[i] << " ";
}

void sub3()
{
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    FOR(i,1,n) cin >> k[i];
    int mx=1,vt=1;
    FOR(i,1,n) f[i]=1;
    bit[a[1]]=mp(1,1);
    FOR(i,2,n)
        FOR(j,0,1000) if (bitcount(a[i]&j)==k[i])
        if(f[i]<bit[j].fi+1)
        {
            f[i]=bit[j].fi+1;
            trace[i]=bit[j].se;
            bit[a[i]]=mp(f[i],i);
            if(mx<f[i]) mx=f[i],vt=i;
        }
    cout << mx <<endl;
    deque<int> g;
    while(mx) g.push_front(vt),mx--,vt=trace[vt];
    FOR(i,0,(int)g.size()-1) cout << g[i] << " ";
}

int main()
{
   

   ios_base::sync_with_stdio(false);
   sub3();
   //if(n>=5000) sub3();else Solve();

}

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