| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1012867 | assazzin_2 | Longest beautiful sequence (IZhO17_subsequence) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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;
}