Submission #1098646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098646		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2889 ms	180224 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e5 + 5;
const int MaxBit = 20;

int n;
int arr[MaxN];
int num[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x];
    }
    for (int x = 1; x <= n; x++)
    {
        cin >> num[x];
    }
}

int Pre[(1 << 20) + 5];
pair<int, int> PreMax[(1 << 10) + 5][(1 << 10) + 5][21];

void Add(int k, int v, int id)
{
    int fi = (k >> 10), se = k & ((1 << 10) - 1);
    for (int mask = 0; mask < (1 << 10); mask++)
    {
        int p = Pre[mask & se];
        PreMax[fi][mask][p] = max(PreMax[fi][mask][p], make_pair(v, id));
    }
}

pair<int, int> GetMax(int k, int v)
{
    int fi = (k >> 10), se = k & ((1 << 10) - 1);
    pair<int, int> res = make_pair(0, 0);
    for (int mask = 0; mask < (1 << 10); mask++)
    {
        int p = Pre[fi & mask];
        if (p > v)
        {
            continue;
        }
        res = max(res, PreMax[mask][se][v - p]);
    }
    return res;
}

int F[MaxN];
int Track[MaxN];

void Exc()
{
    for (int x = 0; x < (1 << 20); x++)
    {
        Pre[x] = __builtin_popcount(x);
    }
    pair<int, int> res = make_pair(0, 0);
    for (int x = 1; x <= n; x++)
    {
        pair<int, int> p = GetMax(arr[x], num[x]);
        F[x] = p.first + 1;
        Track[x] = p.second;
        Add(arr[x], F[x], x);
        res = max(res, make_pair(F[x], x));
    }
    cout << res.first << "\n";
    int p = res.second;
    stack<int> st;
    while (p > 0)
    {
        st.push(p);
        p = Track[p];
    }
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
}

int main()
{
    //freopen("A.INP", "r", stdin);
    //freopen("A.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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