Submission #1264961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264961		dangheo	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	1288 ms	87380 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()
{
}
pair<short, int> jca[512][12][2048];
void Yoshi()
{
    memset(jca, sizeof(jca), 0xff);
    int n;
    cin >> n;
    vector<int> a(n), k(n);
    for (auto &i : a)
        cin >> i;
    for (auto &i : k)
        cin >> i;
    vector<int> dp(n, 1);
    vector<int> trace(n, -1);
    for (int i = 0; i < n; i++)
    {
        for (int low = 0; low < 512; low++)
        {
            const int bp = __builtin_popcount(a[i] & low);
            if (bp > k[i] || k[i] - bp >= 12 || jca[low][k[i] - bp][a[i] >> 9].first < dp[i])
                continue;
            else
            {
                dp[i] = 1 + jca[low][k[i] - bp][a[i] >> 9].first;
                trace[i] = jca[low][k[i] - bp][a[i] >> 9].second;
            }
        }
        int lowBit = a[i] & 511;
        for (int highA = 0; highA < 2048; highA++)
        {
            const int bp = __builtin_popcount(highA & (a[i] >> 9));
            if (jca[lowBit][bp][highA].first < dp[i])
                jca[lowBit][bp][highA] = {dp[i], 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:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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