제출 #1012869

#제출 시각아이디문제언어결과실행 시간메모리
1012869assazzin_2Longest beautiful sequence (IZhO17_subsequence)C++14
100 / 100
2833 ms92996 KiB
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
// #ifndef ONLINE_JUDGE
// #include "dbg.cpp"
// #else
// #define dbg(...)
// #endif
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb(n) push_back(n)
#define F first
#define S second
#define mp(x, y) make_pair(x, y)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define nop cout << -1 << endl;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
const ll sup = 1e18;
const ll inf = -1e18;
const ll mod = 1e9 + 7;
const int N_Max = 3e5 + 7;
const int Nax = 1e6 + 5;
const int LOG = 20;
const int BITS = 30;
const int ALPHA = 26;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}

const int N = 10 ; 
array<int,2> dp[(1 << N)][(1 << N)][11] ;
int a[100005] , k[100005] , pre[100005];  

void solve(){
    int n ; 
    cin >> n ; 
    for(int i = 1 ; i <= n ; i++) cin >> a[i] ; 
    for(int i = 1 ; i <= n ; i++) cin >> k[i] ; 
    int ans = 0 , lst = 0 ; 
    for(int i = 1 ; i <= n ; i++){
        int r = a[i] >> N ;
        int l = a[i] % (1 << N) ; 
        int mx = 1 ;
        pre[i] = i ;
        for(int left = 0 ; left < (1 << N) ; left++){
            int x = __builtin_popcount(left & a[i]) ;
            int rest = k[i] - x ;
            if(rest < 0 || rest > N) continue ; 
            if(dp[left][r][rest][0] + 1 > mx){
                mx = dp[left][r][rest][0] + 1;
                pre[i] = dp[left][r][rest][1] ; 
            }
        }
        if(mx > ans){
            ans = mx ; 
            lst = i ; 
        }
        for(int right = 0 ; right < (1 << N) ; right++){
            int x = __builtin_popcount(right & r) ; 
            if(dp[l][right][x][0] < mx) {
                dp[l][right][x][0] = mx ;
                dp[l][right][x][1] = i ;
            }
        }
    }    

    vector<int> res ;
    while(true){
        res.push_back(lst) ;
        if(pre[lst] == lst) break ;
        lst = pre[lst] ; 
    }
    reverse(res.begin() , res.end()) ; 
    cout << res.size() << endl;
    for(auto x : res) cout << x << " " ;
    cout << endl;
}

int main(){
    FAST
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...