Submission #1266041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266041		dangheo	Longest beautiful sequence (IZhO17_subsequence)	C++17	7 / 100	239 ms	164360 KiB

subsequence

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>

#define hyathu main
#define popcorn __builtin_popcount

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int mmsb = 1e5 + 69, mmb = 1029, mmn = 20, bit = 10;
const ld pi = atan(1) * 4;

/*
Sub 1 (n <= 15): Backtrack (Nothing to say)

Sub 2 (n <= 5000):
 Goi dp[i] = max LSB tu 1...n -> dp[i] = dp[j] + 1 : popcorn(a[i] & a[j]) = k[i]
 -> O(n^2) (still easy)

Sub 3 (n <= 1e5, a[i] <= 2^8):
 Cach 1:
  Goi dp[i][x] = max LSB tu 1...n, ket thuc bang so x -> dp[i][a[i]] = dp[i - 1][j] + 1 : popcorn(a[i], j) = k[i]
   Co the bo di mot chieu do dp[i] chi phu thuoc vao dp[i - 1]
   -> O(n * m) (m = max(a[i]))
 
 Cach 2:
  dp[x] nhu tren mat O(m) de for qua cac x
  -> Them mot chieu dp
  -> dp[x][k] = max(dp[x'] : bitcount(x' & x) = k)
  -> Xet den a[i], ans[i] = dp[a[i]][k[i]], cap nhat lai cho moi dp[y][bitcount(a[i], y)] = max(dp[y][bitcount(a[i], y)], ans[i])
  Van la O(n * m)

Sub 4:
 Cach 1 cua sub 3: O(m) cap nhat ket qua, O(1) cap nhat cac trang thai
 Cach 2 cua sub 3: O(1) cap nhat ket qua, O(m) cap nhat cac trang thai
 
 Van chua du tot -> Can chia ra 2 phan.
 Xet den so a[i], chia ra phan ben trai co b bit, phan ben phai co 20 - b bit.
 Goi phan ben trai la lx, ben phai la rx
 
 Can doi trang thai dp:
    Khi xet den x,
    goi dp[i][rx(x)][k] = l.
        i = lx cua so truoc do
        bitcount(rx, j) = k (j la rx cua so truoc do)
        l = max len
    -> ans[i] = dp[i'][rx(a[i])][k[i] - bitcount(a[i], i')] + 1 (voi moi i' tu 0...2^b)
    Do can biet voi moi j co phan ben trai la i', phan ben phai giao voi rx(a[i]) k bit thi max la bao nhieu
    -> Do phuc tap O(2^b)
 Da tinh xong ans, gio can cap nhat dp.
    -> a[i] co phan ben trai la lx(a[i])
    -> cap nhat tat ca dp[lx(a[i])]
    for tat ca gia tri co the cua phan ben phai, goi la r
    -> maximize(dp[lx(a[i])][r][bitcount(r, rx(a[i]))], ans[i])
    -> Do phuc tap O(2^b)
 
 Can can bang giua 2 viec cap nhat dap an va cap nhat trang thai dp -> Chon b = 1/2 * maxbit la tot nhat -> b = 10.
 
Dieu quan trong cua bai nay: dp khong phai la cho vi tri i, ma la cho gia tri
 -> chia thanh 2 viec: Cap nhat ket qua cho vi tri i, va cap nhat lai bang dp
 -> co the chia ra de do phuc tap giam xuong sqrt

Mot so luu y ve cai dat:
 +, Su dung mang prv de backtrack cho de
 +, Su dung struct de luu thong tin cho de nhin
*/

struct info{
    int len = 0, idx = 0;
};

int n;
info dp[mmb][mmb][mmn];
int a[mmsb], k[mmsb], ans[mmsb], prv[mmsb];

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

inline int L(int x){
    return (x >> bit) & ((1 << bit) - 1);
}

inline int R(int x){
    return x & ((1 << bit) - 1);
}

inline int I(int x, int y){
    return popcorn(x & y);
}

inline bool maxi(int &a, int b){
    if(a < b){
        a = b;
        return 1;
    }
    return 0;
}

void solve(){
    int res = 0, cur = 0;
    
    for(int i = 1; i <= n; ++i){
        //getting ans
        int rx = R(a[i]);
        for(int lf = 0; lf < (1 << bit); ++lf){
            int rem = k[i] - I(L(a[i]), lf);
            const info &p = dp[lf][rx][rem];
            if(maxi(ans[i], p.len))
                prv[i] = p.idx;
        }
        ++ans[i];
        if(ans[i] > res){
            res = ans[i];
            cur = i;
        }
        
        //updating dp
        int lx = L(a[i]);
        for(int rt = 0; rt < (1 << bit); ++rt){
            int cnt = I(rx, rt);
            info &p = dp[lx][rt][cnt];
            if(p.len < ans[i]){
                p.len = ans[i];
                p.idx = i;
            }
        }
    }
    
    cout << res << "\n";
    stack <int> st;
    while(cur != 0){
        st.push(cur);
        cur = prv[cur];
    }
    while(!st.empty()){
        cout << st.top() << " ";
        st.pop();
    }
}

#define filename "test"

int hyathu(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    #ifdef dangheo
    freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    #else
    //freopen(filename".INP", "r", stdin);
    //freopen(filename".OUT", "w", stdout);
    #endif
    
    readData();
    solve();
    
    return 0;
}

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