Submission #1123200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123200		KALARRY	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	109 ms	1948 KiB

subsequence

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,a[100005],k[100005],dp[100005],par[100005],best_emf[1000005]; //par[i][j] = finishing at i having lenght %d

void print_path(int i)
{
    if(i==0)
        return;
    print_path(par[i]);
    printf("%d ",i);
}

int main()
{
    scanf("%d",&N);
    int max_elem = 0;
    for(int i = 1 ; i <= N ; i++)
    {
        scanf("%d",&a[i]);
        max_elem = max(max_elem,a[i]);
    }
    for(int i = 1 ; i <= N ; i++)
        scanf("%d",&k[i]);
    int ans = 0;
    int pos = 0;
    if(N <= 5000)
    {
        for(int i = 1 ; i <= N ; i++)
        {
            dp[i] = 1;
            par[i] = 0;
            for(int j = 1 ; j < i ; j++)
                if(__builtin_popcount(a[j] & a[i])==k[i] && dp[j] + 1 > dp[i])
                {
                    dp[i] = dp[j] + 1;
                    par[i] = j;
                }
            if(dp[i] > ans)
            {
                ans = dp[i];
                pos = i;
            }
        }
    }
    else
    {
        for(int i = 1 ; i <= N ; i++)
        {
            dp[i] = 1;
            par[i] = 0;
            for(int mask = 0 ; mask < max_elem ; mask++)
                if(__builtin_popcount(a[i] & mask) == k[i] && dp[best_emf[mask]] + 1 > dp[i])
                {
                    dp[i] = dp[best_emf[mask]] + 1;
                    par[i] = best_emf[mask];
                }
            if(dp[i] > dp[best_emf[a[i]]])
                best_emf[a[i]] = i;
            if(dp[i] > ans)
            {
                ans = dp[i];
                pos = i;
            }
        }
    }
    printf("%d\n",ans);
    print_path(pos);
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
subsequence.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
subsequence.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d",&k[i]);
      |         ~~~~~^~~~~~~~~~~~

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