oj.uz

Submission #474062

# Submission time Handle Problem Language Result Execution time Memory
474062 2021-09-16T18:28:04 Z ogibogi2004 Longest beautiful sequence (IZhO17_subsequence) C++14
0 / 100
 6 ms 4684 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int MAXA=(1<<20);
const int MAXHALF=(1<<10);
int n;
int a[MAXN];
int k[MAXN];
int maxlen[MAXHALF][MAXHALF][22];
int cntbits[MAXHALF][MAXHALF];
int dp[MAXN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)cin>>k[i];
    for(int i1=0;i1<MAXHALF;++i1)
    {
        for(int i2=0;i2<MAXHALF;++i2)
        {
            cntbits[i1][i2]=__builtin_popcount(i1&i2);
        }
    }
    int maxdp=0;
    for(int i=1;i<=n;++i)
    {
        dp[i]=1;
        int a1=a[i]/MAXHALF,a2=a[i]%MAXHALF;
        for(int j=0;j<MAXHALF;++j)
        {
            int t=cntbits[a1][j];
            if(t>k[i])continue;
            dp[i]=max(dp[i],maxlen[j][a2][k[i]-t]);
        }
        for(int j=0;j<MAXHALF;++j)
        {
            maxlen[a1][j][cntbits[j][a2]]=max(maxlen[a1][j][cntbits[j][a2]],dp[i]);
        }
        maxdp=max(maxdp,dp[i]);
    }
    cout<<maxdp<<'\n';
    vector<int>v;
    for(int i=n;i>=1;i--)
    {
        if(dp[i]==maxdp)
        {
            v.push_back(i);
            break;
        }
    }
    for(int i=v.back()-1;i>0;i--)
    {
        if(dp[i]==dp[v.back()]-1&&__builtin_popcount(a[i]&a[v.back()])==k[v.back()])
        {
            v.push_back(i);
        }
    }
    reverse(v.begin(),v.end());
    for(auto xd:v)
    {
        cout<<xd<<" ";
    }
    cout<<'\n';
return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4684 KB jury has the better answer: jans = 4, pans = 1
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4684 KB jury has the better answer: jans = 4, pans = 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4684 KB jury has the better answer: jans = 4, pans = 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4684 KB jury has the better answer: jans = 4, pans = 1
2 Halted 0 ms 0 KB -