Submission #1264724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264724		yoshi_33550336	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	1388 ms	96540 KiB

subsequence

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#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;
    vector<vector<vector<int>>> jca(11, vector<vector<int>>(1024, vector<int>(1024, -1)));
    vector<vector<vector<int>>> jcat(11, vector<vector<int>>(1024, vector<int>(1024, -1)));
    vector<int> dp(n, 1);
    vector<int> trace(n, -1);
    for (int i = 0; i < n; i++)
    {
        for (int low = 0; low < 1024; low++)
        {
            const int bp = __builtin_popcountll(a[i] & low);
            if (bp > k[i] || k[i] - bp >= 11 || jca[k[i] - bp][low][a[i] >> 10] < dp[i])
                continue;
            else
            {
                dp[i] = 1 + jca[k[i] - bp][low][a[i] >> 10];
                trace[i] = jcat[k[i] - bp][low][a[i] >> 10];
            }
        }
        int lowBit = a[i] & 1023;
        for (int highA = 0; highA < 1024; highA++)
        {
            const int bp = __builtin_popcountll(highA & (a[i] >> 10));
            if (jca[bp][lowBit][highA] < dp[i])
            {
                jcat[bp][lowBit][highA] = i;
                jca[bp][lowBit][highA] = 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:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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