Submission #1264707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264707		yoshi_33550336	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	72 ms	1860 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<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] = dp[j] + 1, trace[i] = jct[a[i]];
            if (dp[i] > jc[a[i]])
                jc[a[i]] = dp[i], jct[a[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:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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