Submission #855152

#	Time	Username	Problem	Language	Result	Execution time	Memory
855152		Alfraganus	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	199 ms	1884 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

#define fs first
#define ss second
#define endl '\n'
#define all(a) a.begin(), a.end()

#define print(a)          \
    for (auto x : a)      \
        cout << x << ' '; \
    cout << endl;

#define printmp(a)   \
    for (auto x : a) \
        cout << x.fs << ' ' << x.ss << endl;

int BitCount(int n){
    int ans = 0;
    while(n){
        if((n & 1))
            ans ++;
        n >>= 1;
    }
    return ans;
}

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n), k(n);
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    for(int j = 0; j < n; j ++)
        cin >> k[j];
    if(n <= 5000){
        vector<int> dp(n), maxs(n);
        int ans = 0, in = 0;
        for(int i = 0; i < n; i ++){
            int mx = 0, index = -1;
            for(int j = i - 1; j >= 0; j --){
                if(BitCount(a[i] & a[j]) == k[i] and mx < maxs[j] + 1){
                    mx = maxs[j] + 1;
                    index = j;
                }
            }
            dp[i] = index;
            maxs[i] = mx;
            if(ans < mx){
                ans = mx;
                in = i;
            }
        }
        cout << ans + 1 << endl;
        vector<int> p;
        while(in != -1)
            p.push_back(in + 1), in = dp[in];
        reverse(all(p));
        print(p)
    }
    else{
        vector<int> dp(n), maxs(n, -1), bitmask(1 << 9, -1);
        int ans = 0, s = 0;
        for(int i = 0; i < n; i ++){
            int mx = 0, index = -1;
            for(int j = 0; j < (1 << 9); j ++){
                if(bitmask[j] != -1 and BitCount(a[i] & j) == k[i] and mx < maxs[bitmask[j]] + 1){
                    mx = maxs[bitmask[j]] + 1;
                    index = bitmask[j];
                }
            }
            // if(maxs[i] < mx)
            bitmask[a[i]] = i;
            dp[i] = index;
            maxs[i] = mx;
            if(ans < mx){
                ans = mx;
                s = i;
            }
        }
        cout << ans + 1 << endl;
        vector<int> p;
        while (s != -1)
            p.push_back(s + 1), s = dp[s];
        reverse(all(p));
        print(p)
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("subsequence.in", "r", stdin);
    // freopen("subsequence.out", "w", stdout);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

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