Submission #38254

#	Time	Username	Problem	Language	Result	Execution time	Memory
38254		antimirage	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	179 ms	41220 KiB

subsequence

#include <iostream>
#include <vector>
#include <deque>
#include <math.h>
#include <set>
#include <iomanip>
#include <time.h>
#include <list>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <memory.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )

using namespace std;

const int N = 2e6 + 5;

int n, a[N], b[N], dp[N], ans, p[N], res;

int mx[N];

vector <int> path;

main ()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]), dp[i] = 1;
        if (!mx[ a[i] ])
            mx[ a[i] ] = i;
    }
    if (n > 5000)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < 256; j++)
            {
                if ( __builtin_popcount(a[i] & j) == b[i] )
                {
                    if (mx[j] < i && dp[i] < dp[ mx[j] ] + 1)
                    {
                        p[i] = mx[j];
                        dp[i] = dp[ mx[j] ] + 1;
                    }
                }
            }
            if ( dp[ mx[a[i]] ] < dp[i] )
                mx[ a[i] ] = i;
        }
        for (int i = 1; i <= n; i++)
        {
            if (dp[i] > ans)
            {
                ans = dp[i];
                res = i;
            }
        }
        cout << ans << endl;

        while (res)
        {
            path.pb( res );
            res = p[res];
        }
        reverse(all(path));
        for (auto x : path)
            printf("%d ", x);
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = i - 1; j >= 1; j--)
            {
                if ( __builtin_popcount(a[i] & a[j]) == b[i] )
                {
                    if (dp[i] < dp[j] + 1)
                    {
                        p[i] = j;
                        dp[i] = max( dp[i], dp[j] + 1 );
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++)
        {
            if (dp[i] > ans)
            {
                ans = dp[i];
                res = i;
            }
        }
        cout << ans << endl;

        while (res)
        {
            path.pb( res );
            res = p[res];
        }
        reverse(all(path));
        for (auto x : path)
            printf("%d ", x);
    }
}
/**
4
1 2 3 4
10 0 1 0
**/

Compilation message (stderr)

subsequence.cpp:33:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:37:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
                           ^
subsequence.cpp:41:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]), dp[i] = 1;
                                      ^

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