Submission #337962

#	Time	Username	Problem	Language	Result	Execution time	Memory
337962		spike1236	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	341 ms	262148 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.1415926535897932384626433832795;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

const int MAXN = (1 << 20) + 10;
int n;
int dp[MAXN];
int a[MAXN];
int k[MAXN];
int bp[MAXN];
int p[MAXN][2];

void solve() {
    for(int i = 0; i < (1 << 20); ++i) bp[i] = __builtin_popcount(i);
    cin >> n;
    int mxb = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        for(int j = 19; j >= 0; --j) {
            if((a[i] >> j) & 1) {
                mxb = max(mxb, j);
                break;
            }
        }
    }
    for(int i = 1; i <= n; ++i)
        cin >> k[i];
    memset(dp, -1, sizeof(dp));
    memset(p, -1, sizeof(p));
    if(n <= 5000) {
        for(int i = 1; i <= n; ++i) {
            dp[i] = 1;
            for(int j = 1; j < i; ++j)
                if(bp[a[i] & a[j]] == k[i]) {
                    if(dp[j] + 1 > dp[i]) {
                        p[i][0] = j;
                        dp[i] = dp[j] + 1;
                    }
                }
        }
        int mx = max_element(dp + 1, dp + n + 1) - dp;
        veci ans;
        while(mx != -1) {
            ans.pb(mx);
            mx = p[mx][0];
        }
        reverse(all(ans));
        cout << sz(ans) << '\n';
        for(auto it : ans) cout << it << ' ';
        return;
    }
    if(mxb <= 8) {
        for(int i = 1; i <= n; ++i) {
            if(dp[a[i]] < 1) {
                dp[a[i]] = 1;
                p[a[i]][0] = i;
                p[a[i]][1] = -1;
            }
            for(int j = 0; j < (1 << (mxb + 1)); ++j) {
                if((~dp[j]) && bp[a[i] & j] == k[i]) {
                    if(dp[j] + 1 > dp[a[i]]) {
                        dp[a[i]] = dp[j] + 1;
                        p[a[i]][0] = i;
                        p[a[i]][1] = j;
                    }
                }
            }
        }
        int pos = max_element(dp, dp + (1 << (mxb + 1))) - dp;
        veci ans;
        while(pos != -1) {
            ans.pb(p[pos][0]);
            pos = p[pos][1];
        }
        reverse(all(ans));
        cout << sz(ans) << '\n';
        for(auto it : ans) cout << it << ' ';
        return;
    }
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    ///cin >> T;
    while(T--) solve(), cout << '\n';
    return 0;
}

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