Submission #211305

#	Time	Username	Problem	Language	Result	Execution time	Memory
211305		vinhhung053	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	403 ms	4088 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()
{
    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()
{
    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,256) 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;
                if(mx<f[i]) mx=f[i],vt=i;
            }
        if (f[i] > bit[a[i]].fi) bit[a[i]]=mp(f[i],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 Rand(ll l, ll r)
{
    return l+(rand()*rand()+rand()) % (r-l+1);
}


void sinh()
{
    freopen("text.inp","w",stdout);
    int n=100000;
    cout << n << endl;
    FOR(i,1,n) cout << Rand(0,200)<< " " ;
    cout<<endl;
    FOR(i,1,n) cout << Rand(0,20) << " ";
}

int main()
{

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

}

Compilation message (stderr)

subsequence.cpp: In function 'void sinh()':
subsequence.cpp:116:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("text.inp","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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