Submission #497056

#	Time	Username	Problem	Language	Result	Execution time	Memory
497056		NehaDalmia	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3934 ms	97132 KiB

subsequence

#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#define ll long long
#define mod 998244353
#define mod1 998244353
using namespace std;


vector<int>cand;
vector<int> prime(1000005);  
vector<ll>primes;
void SieveOfEratosthenes(int n) 
{ 
    for (ll p=2; p*p<=n; p++) 
    { 
        if (prime[p] == 0 ) 
        { 
            for (int i=p*p; i<=n; i += p) 
                if(prime[i]==0)
                prime[i] = p; 
        } 
    } 
  
    
} 

long long power(long long x, long long  y )
{  
    if(y<0ll)
    return 0;
    long long res = 1ll;     
    x = x % mod; 
    if (x == 0ll) return 0; 
    while (y > 0ll)  
    {  
        if (y & 1ll)  
            res = (res*x) % mod;  
        y = y>>1ll; 
        x = (x*x) % mod;  
    }  
    return res;  
}  
long long add(long long x, long long y)
{
    x%=mod;
    y%=mod;
   
    return (x+y)%mod;
}
 
long long mul(long long x, long long y)
{
    return ((x%mod) * 1ll * (y%mod)) % mod;
}
 
long long binpow(long long x, long long y)
{
    if(y==0)
    return 1ll;
    long long z = 1ll;
    x%=mod;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1ll;
    }
    return z;
}
 
long long inv(long long x)
{
    return binpow(x, mod - 2);
}
 
long long divide(long long x, long long y)
{
    return mul(x, inv(y));
}
 
long long fact[200006];
 
void precalc()
{
    fact[0] = 1;
    for(long long i = 1; i < 200006; i++)
        fact[i] =(fact[i - 1]*i)%mod;
      //fact[i]=fact[i-1]*i;
}
 
long long C(long long n, long long k)
{
    if(n<k)
    return 0;
    if(k<0)
    return 0;
    if(n==0)
    return 1;
    return divide(fact[n], mul(fact[k], fact[n - k]));
    //return (fact[n]/(fact[n-k]))/fact[k];
}
long long sub(long long A,long long B)
{
    return (A-B+mod)%mod;
}

// int matrixdim;
// struct M {
//     vector<vector<int>> t;
//     M() {
//         t.resize(matrixdim,vector<int>(matrixdim));
//     }
//     M operator* (const M& b) const {
//         M c = M();
//         int n=matrixdim;
//         for(int i = 0; i < n; ++i) {
//             for(int j = 0; j < n; ++j) {
//                 for(int k = 0; k < n; ++k) {
//                     c.t[i][k]=add(c.t[i][k], mul(b.t[i][j], t[j][k]));
//                 }
//             }
//         }
//         return c;
//     }
// }
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

    // order_of_key (k)

    // find_by_order(k)
pair<int,int> best[(1<<10)][(1<<10)][11];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout<<fixed<<setprecision(12);
    cerr<<fixed<<setprecision(5);
    int t=1;
    //SieveOfEratosthenes(1000002);
    //precalc();
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    //cin>>t;     
    while(t--)
    {
       int n;
       cin>>n;
       
       int dp[n]={0};
       int parent[n]={0};
       
       int i,j,k;
       for(i=0;i<(1<<10);i++)
       {
           for(j=0;j<(1<<10);j++)
           {
               for(k=0;k<=10;k++)
                best[i][j][k]={0,0};
           }
       }
       int A[n];
       int B[n];
       for(i=0;i<n;i++)
       {
           cin>>A[i];
       }
       for(i=0;i<n;i++)
       {
           cin>>B[i];
       }
       int ans = 1;
       for(i=0;i<n;i++)
       {
           dp[i]=1;
           int left=0,right=0;
           for(j=0;j<10;j++)
           {
               if(A[i]&(1<<(j+10)))
                left|=(1<<j);
               if(A[i]&(1<<j))
                right|=(1<<j);
           }
           for(j=0;j<(1<<10);j++)
           {
               int x = __builtin_popcount(left&j);
               if(x>B[i]||B[i]-x>10)
                continue;

               if(dp[i]<1+best[j][right][B[i]-x].first)
               {
                   
                   dp[i]=1+best[j][right][B[i]-x].first;
                   parent[i]=best[j][right][B[i]-x].second;
               }
           }
           for(j=0;j<(1<<10);j++)
           {
               int x = __builtin_popcount(right&j);
               if(best[left][j][x].first<dp[i])
               {
                   best[left][j][x].first=dp[i];
                   best[left][j][x].second=i+1;
               }
           }
           ans = max(ans,dp[i]);
       }
       cout<<ans<<"\n";
       for(i=0;i<n;i++)
       {
           if(ans==dp[i])
            break;
       }
       vector<int>ans1;
       while(i>=0)
       {
           ans1.push_back(i+1);
           i = parent[i]-1;
       }
       while(ans1.size()!=0)
       {
           cout<<ans1.back()<<" ";
           ans1.pop_back();
       }
       
    }
    return 0;

}

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