제출 #156217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156217		andrew	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	4965 ms	116604 KiB

subsequence

#include <bits/stdc++.h>

//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 1e6 + 2;
const ll inf = 3e18;
ll buben = 2000;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T> void vout(T s){cout << s << endl;exit(0);}

int Dp[MAXN], Wh[MAXN];

pii DP[MAXN][21];

vector <int> v[21], v1[MAXN];

bool f[MAXN];

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;

    vector <ll> a(n + 1), k(n + 1);

    for(int i = 1; i <= n; i++)cin >> a[i];
    for(int i = 1; i <= n; i++)cin >> k[i];

    vector <ll> dp(n + 1), pr(n + 1);

    for(int i = 0; i < pw(20); i++){
        v[__builtin_popcount(i)].p_b(i);
        for(int j = 0; j < 20; j++)if((i & pw(j)))v1[i].p_b(j);
    }

    for(int i = 0; i <= 20; i++)shuffle(all(v[i]), rnd);

    if(n <= 5000){
         for(int i = 1; i <= n; i++){
                dp[i] = 1;
                pr[i] = 0;
                for(int j = 1; j < i; j++)if(__builtin_popcountll(a[i] & a[j]) == k[i]){
                    if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        pr[i] = j;
                    }
                }
            }

            ll Mx = *max_element(dp.begin() + 1, dp.end());

            cout << Mx << "\n";

            for(int i = 1; i <= n; i++)if(dp[i] == Mx){
                ll x = i;
                vector <ll> ans;
                while(x){
                    ans.p_b(x);
                    x = pr[x];
                }

                reverse(all(ans));
                for(auto i : ans)cout << i << " ";
                cout << "\n";
                return 0;

            }
    }

    if(*max_element(a.begin() + 1, a.end()) < pw(8)){
        for(int i = 1; i <= n; i++){
            dp[i] = 1;
            pr[i] = 0;

            for(int j = 0; j < pw(8); j++)if(__builtin_popcountll(a[i] & j) == k[i]){
                if(dp[i] < Dp[j] + 1){
                    dp[i] = Dp[j] + 1;
                    pr[i] = Wh[j];
                }
            }

            if(Dp[a[i]] < dp[i]){
                Dp[a[i]] = dp[i];
                Wh[a[i]] = i;
            }
        }

        ll Mx = *max_element(dp.begin() + 1, dp.end());

        cout << Mx << "\n";

        for(int i = 1; i <= n; i++)if(dp[i] == Mx){
            ll x = i;
            vector <ll> ans;
            while(x){
                ans.p_b(x);
                x = pr[x];
            }

            reverse(all(ans));
            for(auto i : ans)cout << i << " ";
            cout << "\n";
            return 0;

        }
    }

    ll last = 1;

     for(int i = 1; i <= n; i++){
        if(i % buben == 0){
            last = i;
            for(int j = pw(20) - 1; j >= 0; j--){
                for(auto x : v1[j]){
                    if(Dp[j ^ pw(x)] < Dp[j]){
                        Dp[j ^ pw(x)] = Dp[j];
                        Wh[j ^ pw(x)] = Wh[j];
                    }
                }
            }
            for(int i = 0; i <= 20; i++)if(!v[i].empty())shuffle(all(v[i]), rnd);
        }
        dp[i] = 1;
        pr[i] = 0;
        for(int j = last; j < i; j++)if(__builtin_popcountll(a[i] & a[j]) == k[i]){
            if(dp[i] < dp[j] + 1){
                dp[i] = dp[j] + 1;
                pr[i] = j;
            }
        }

        ll x = k[i];
        if(x >= 0){
            for(int j = 0; j < min(ll(v[x].size()), 500ll); j++){
                if(__builtin_popcountll(a[i] & v[x][j]) == k[i]){
                    if(dp[i] < Dp[v[x][j]] + 1){
                        dp[i] = Dp[v[x][j]] + 1;
                        pr[i] = Wh[v[x][j]];
                    }
                }
            }
        }

        if(DP[a[i]][k[i]].fi + 1 > dp[i]){
            dp[i] = DP[a[i]][k[i]].fi + 1;
            pr[i] = DP[a[i]][k[i]].se;
        }

        if(Dp[a[i]] < dp[i]){
            Dp[a[i]] = dp[i];
            Wh[a[i]] = i;
        }
    }

    ll Mx = *max_element(dp.begin() + 1, dp.end());

    cout << Mx << "\n";

    for(int i = 1; i <= n; i++)if(dp[i] == Mx){
        ll x = i;
        vector <ll> ans;
        while(x){
            ans.p_b(x);
            x = pr[x];
        }

        reverse(all(ans));
        for(auto i : ans)cout << i << " ";
        cout << "\n";
        return 0;

    }

    return 0;
}

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