Submission #710827

#TimeUsernameProblemLanguageResultExecution timeMemory
710827MinaRagy06Longest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
6014 ms3152 KiB
#include <bits/stdc++.h>
using namespace std;
#define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl    '\n'
#define int     long long

signed main()
{
    lesgooo;
    int n;
    cin >> n;
    int a[n], b[n]{};
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    int dp[n]{};
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++) if (__builtin_popcount(a[i] & a[j]) == b[i]) dp[i] = max(dp[i], dp[j]);
        dp[i]++;
    }
    int mx = 0, pos = 0;
    for (int i = 0; i < n; i++)
    {
        if (dp[i] > mx) mx = dp[i], pos = i;
    }
    stack<int> s;
    while (dp[pos] > 1)
    {
        s.push(pos);
        for (int j = 0; j < pos; j++) if (__builtin_popcount(a[pos] & a[j]) == b[pos] && dp[j] + 1 == dp[pos]) {pos = j; break;}
    }
    cout << s.size()+1 << endl;
    cout << pos+1 << " ";
    while (s.size()) cout << s.top()+1 << " ", s.pop();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...