Submission #921997

#	Time	Username	Problem	Language	Result	Execution time	Memory
921997		phong	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	391 ms	22652 KiB

subsequence

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 2e5 + 100;
const ll oo = 1e18, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 7;
#define pii pair<int, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;

int n, k[nmax], a[nmax];

namespace subtask2{
    int dp[nmax];
    bool check(){
        if(n <= 5e3) return 1;
        return 0;
    }
    void sol(){
        int ans = 0;

        for(int i = 1; i <= n; ++i){
            dp[i] = 1;
            for(int j = 1; j < i; ++j){
                int x = __builtin_popcount(a[i] & a[j]);
//                cout << x << ' ';
                if(x == k[i]){
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
//            cout << "\n";
            ans = max(ans, dp[i]);
        }
        cout << ans << "\n";
        vector<int> v;
        for(int i = 1; i <= n; ++i){
            if(dp[i] == ans){
                int id = i;
                while(ans > 0){
                    v.push_back(id);
                    for(int j = 1; j < id; ++j){
                        int x = __builtin_popcount(a[id] & a[j]);
//                cout << x << ' ';
                        if(x == k[id] && dp[id] == dp[j] + 1){
                            id = j;
                            break;
                        }
                    }
                    --ans;
                }
            }
        }
        reverse(v.begin(), v.end());
        for(auto p : v) cout << p << ' ';
    }
}

namespace subtask3{
    int trace[nmax];
    bool check(){
        if(*max_element(a + 1, a + 1 + n) < (1 << M)) return 1;
        return 0;
    }

    int gg[nmax];
    void sol(){
        int ans = 0;
        vector<pii> dp, f;
        dp.resize(1 << M);
        f.resize(1 << M);
        for(int i = 1; i <= n; ++i){
            for(int msk = 0; msk < (1 << M); ++msk){
                int x = __builtin_popcount(msk & a[i]);
                if(x == k[i]){
                    int &cur = dp[a[i]].fi;
                    if(cur < f[msk].fi + 1){
                        cur = f[msk].fi + 1;
                        trace[i] = f[msk].se;
                    }
                }
            }
            dp[a[i]].fi = max(dp[a[i]].fi, 1);
            for(int msk = 0; msk < (1 << M); ++msk){
                if(dp[msk].fi != f[msk].fi){
                    dp[msk].se = i;
                }
                gg[i] = max(gg[i], dp[msk].fi);
            }
            f = dp;
        }
        int id = 0;
        for(int i = 1; i <= n; ++i){
            if(gg[id] < gg[i]){
                id = i;
            }
        }
        cout << gg[id] << "\n";
        vector<int> v;
        while(id > 0){
            v.push_back(id);
            id = trace[id];
        }
        reverse(v.begin(), v.end());
        for(auto p : v) cout << p << ' ';
//        for(int )
    }
}

namespace subtask4{
    pii dp[1 << M][21][1 << M];
    int f[nmax], trace[nmax];
    int bit(int msk, int x){
        return msk >> x & 1;
    }
    void sol(){
        for(int i = 1; i <= n; ++i){
            f[i] = 1;
            int pre = 0, suf = 0;
            for(int j = 0; j < M; ++j){
                if(bit(a[i], j)) pre |= 1 << j;
            }
            for(int j = M; j < 2 * M; ++j){
                if(bit(a[i], j)) suf |= 1 << j;
            }
            for(int msk = 0; msk < (1 << M); ++msk){
                int x = __builtin_popcount(suf& msk);
                if(x <= k[i]){
                    auto cur = dp[pre][k[i] - x][msk];
                    if(f[i] < cur.fi + 1){
                        f[i] = cur.fi + 1;
                        trace[i] = cur.se;
                    }
                }
            }
            for(int msk = 0; msk < (1 << M); ++msk){
                int x = __builtin_popcount(msk & pre);
                auto &cur = dp[msk][x][suf];
                if(cur.fi < f[i]) cur = {f[i], i};
            }
        }
        int id = 0;
        for(int i = 1; i <= n; ++i){
            if(f[id] < f[i]){
                id = i;
            }
        }
        cout << f[id] << "\n";
        vector<int> v;
        while(id > 0){
            v.push_back(id);
            id = trace[id];
        }
        reverse(v.begin(), v.end());
        for(auto p : v) cout << p << ' ';
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> k[i];
    if(subtask2::check()) return subtask2::sol(), 0;
    if(subtask3::check()) return subtask3::sol(), 0;
    subtask4::sol();

}
/*
4
1 2 3 4
10 0 1 0
5
5 3 5 3 5
10 1 20 1 20
*/

Compilation message (stderr)

subsequence.cpp: In function 'void subtask3::sol()':
subsequence.cpp:73:13: warning: unused variable 'ans' [-Wunused-variable]
   73 |         int ans = 0;
      |             ^~~
subsequence.cpp: At global scope:
subsequence.cpp:163:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  163 | main(){
      | ^~~~

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