Submission #1264715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264715		yoshi_33550336	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	87 ms	1864 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
void Yoshi()
{
    int n;
    cin >> n;
    vector<int> a(n), k(n);
    for (auto &i : a)
        cin >> i;
    for (auto &i : k)
        cin >> i;
    if (n <= 5000)
    {
        vector<int> dp(n, 1);
        vector<int> trace(n, -1);
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
                if (__builtin_popcountll(a[i] & a[j]) == k[i] && dp[j] + 1 > dp[i])
                    dp[i] = dp[j] + 1, trace[i] = j;
        int pos = max_element(dp.begin(), dp.end()) - dp.begin();
        cout << dp[pos] << endl;
        deque<int> dq;
        while (pos != -1)
        {
            dq.push_front(pos + 1);
            pos = trace[pos];
        }
        for (auto &i : dq)
            cout << i << " ";
        cout << endl;
    }
    else
    {
        vector<int> jc(256, -1);
        vector<int> jct(256, -1);
        vector<vector<vector<int>>> jca(16, vector<vector<int>>(16, vector<int>(4, -1)));
        vector<int> dp(n, 1);
        vector<int> trace(n, -1);
        jc[a[0]] = 1;
        jct[a[0]] = 0;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < 256; j++)
                if (__builtin_popcountll(a[i] & j) == k[i] && jc[j] + 1 > dp[i])
                    dp[i] = jc[j] + 1, trace[i] = jct[j];
            dp[i] = 0;
            for (int low = 0; low < 16; low++)
                if (__builtin_popcountll(a[i] & low) > k[i])
                    continue;
                else
                    dp[i] = max(1 + jca[low][a[i] >> 4][k[i] - __builtin_popcountll(a[i] & low)], dp[i]);
            if (dp[i] > jc[a[i]])
                jc[a[i]] = dp[i], jct[a[i]] = i;
            int lowBit = a[i] & 15;
            for (int highA = 0; highA < 16; highA++)
                jca[lowBit][highA][__builtin_popcountll(highA & (a[i] >> 4))] =
                    max(jca[lowBit][highA][__builtin_popcountll(highA & (a[i] >> 4))], dp[i]);
        }
        int pos = max_element(dp.begin(), dp.end()) - dp.begin();
        cout << dp[pos] << endl;
        deque<int> dq;
        while (pos != -1)
        {
            dq.push_front(pos + 1);
            pos = trace[pos];
        }
        for (auto &i : dq)
            cout << i << " ";
        cout << endl;
    }
}
signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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