Submission #807865

#	Time	Username	Problem	Language	Result	Execution time	Memory
807865		hanifchdn	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	75 ms	1480 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 1e5 + 5;

int a[N], k[N], dp1[N], ans[N];
pair<int, int> dp2[N];
vector<int> v;

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> k[i];
    if (n <= 5000) {
        for (int i = 1; i <= n; i++) dp1[i] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (__builtin_popcount(a[i] & a[j]) != k[i] or dp1[i] > dp1[j]) continue;
                dp1[i] = dp1[j] + 1, ans[i] = j;
            }
        }
        int id = 0;
        for (int i = 1; i <= n; i++) if (dp1[i] > dp1[id]) id = i;
        cout << dp1[id] << "\n";
        while (id != 0) {
            v.push_back(id);
            id = ans[id];
        }
        reverse(v.begin(), v.end());
        for (auto x : v) cout << x << " ";
        cout << "\n";
    }
    else {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < (1 << 8); j++) {
                if (__builtin_popcount(a[i] & j) != k[i] or dp2[a[i]].fi > dp2[j].fi) continue;
                dp2[a[i]].fi = dp2[j].fi + 1, ans[i] = dp2[j].se, dp2[a[i]].se = i;
            }
            if (dp2[a[i]].fi == 0) dp2[a[i]].fi = 1, dp2[a[i]].se = i;
        }
        int id = 0;
        for (int i = 1; i <= n; i++) if (dp2[a[i]].fi > dp2[a[id]].fi) id = i;
        cout << dp2[a[id]].fi << "\n";
        while (id != 0) {
            v.push_back(id);
            id = ans[id];
        }
        reverse(v.begin(), v.end());
        for (auto x : v) cout << x << " ";
        cout << "\n";
    }
}  

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