Submission #1256975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256975		DangKhoizzzz	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3380 ms	100612 KiB

subsequence

#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int maxn = 2e5 + 7;

int n , a[maxn] , b[maxn] , trace[maxn] , f[5005];
pii dp[(1 << 10) + 5][(1 << 10) + 5][12];

void solve2()
{
    pii ans = {1 , 1};
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1; // trace[i] = 0;

        for(int j = 1; j < i; j++)
        {
            if(f[j] + 1 > f[i] && __builtin_popcount(a[i]&a[j]) == b[i])
            {
                f[i] = f[j] + 1;
                trace[i] = j;
            }
        }
        ans = max(ans , (pii){f[i] , i});
    }
    vector <int> path;
    int pos = ans.se;
    while(pos != 0)
    {
        path.push_back(pos);
        pos = trace[pos];
    }
    reverse(path.begin() , path.end());
    cout << path.size() << '\n';
    for(int x: path) cout << x << ' ';
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];

    if(n <= 5000) {solve2(); return;}

    pii ans = {1 , 1};

    for(int i = 1; i <= n; i++)
    {
        int pre = (a[i] >> 10) , suf = a[i]%(1 << 10) , cur = 1;

        for(int mask = 0; mask < (1 << 10); mask++)
        {
            int k = b[i] - __builtin_popcount(pre&mask);
            if(k < 0 || k > 10) continue;
            if(dp[mask][suf][k].fi + 1 > cur)
            {
                cur = dp[mask][suf][k].fi + 1;
                trace[i] = dp[mask][suf][k].se;
            }
        }
        for(int mask = 0; mask < (1 << 10); mask++)
        {
            int k = __builtin_popcount(suf&mask);
            dp[pre][mask][k] = max(dp[pre][mask][k] , (pii){cur , i});
        }
        ans = max(ans , {cur , i});
    }

    vector <int> path;
    int pos = ans.se;
    while(pos != 0)
    {
        path.push_back(pos);
        pos = trace[pos];
    }
    reverse(path.begin() , path.end());
    cout << path.size() << '\n';
    for(int x: path) cout << x << ' ';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

/*

sinhtest.cpp 

// ch? stress m?i s? l??ng ko tress trace


#include <bits/stdc++.h>
using namespace std;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd

long long Rand(long long L, long long R)
{
    assert(L <= R);
    return L + rd() % (R - L + 1);
}

int main()
{
    srand(time(NULL));
    for (int iTest = 1; iTest <= 100; iTest++)
    {
        ofstream inp ("test.inp");
        int n = 5000;

        inp << n << '\n';
        for(int i = 1; i <= n; i++)
        {
            inp << Rand(0 , 1 << 20) << ' ';
        }
        inp << '\n';
        for(int i = 1; i <= n; i++)
        {
            inp << Rand(0 , 20) << ' ';
        }
        inp << '\n';
        inp.close();
        system("test.exe");
        system("testtrau.exe");
        if(system("fc test.out testtrau.out") != 0)
        {
            cout << "WA" << '\n'; return 0;
        }
        else cout << "AC" << '\n';
    }
    return 0;
}

*/

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