Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <string>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <queue>
- #include <ctime>
- #define pb push_back
- #define ll long long
- #define mp make_pair
- #define f first
- #define s second
- #define pii pair < int, int >
- #define ull unsigned long long
- #define pll pair < ll, ll >
- #define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
- #define all(s) s.begin(), s.end()
- #define sz(a) (int)a.size()
- const int inf = (1ll << 30) - 1;
- const int maxn = (int) 1e5 + 10;
- using namespace std;
- int dp[(1<<20)+ 10][10 + 3];
- int a[100100];
- int prv[100100];
- int k[100100];
- int mx[100100];
- int cnt[(1<<10) + 10];
- int n;
- void solve(){
- scanf("%d", &n);
- for(int i = 1; i <= n; i++){
- scanf("%d", &a[i]);
- }
- for(int i = 1; i <= n; i++){
- scanf("%d", &k[i]);
- }
- for(int i = 0; i < (1<<10); i++)
- cnt[i] = __builtin_popcount(i);
- for(int i = 1; i <= n; ++i){
- int x = a[i] & ((1<<10)-1);
- int y = (a[i] >> 10) & ((1<<10)-1);
- int &cur = mx[i];
- int &ind = prv[i];
- for(int mask = 0; mask < (1<<10); mask++){
- int K = k[i] - cnt[mask & y];
- if(K < 0 || K > 10) continue;
- int &cc = dp[(mask<<10)|x][K];
- if(mx[cc] > cur){
- cur = mx[cc];
- ind = cc;
- }
- }
- cur++;
- for(int mask = 0; mask < (1<<10); ++mask){
- int K = cnt[mask & x];
- int &cc = dp[(y<<10)|mask][K];
- if(mx[cc] < cur){
- cc = i;
- }
- }
- }
- int j = 0;
- for(int i = 1; i <= n; i++){
- if(mx[j] < mx[i]){
- j = i;
- }
- }
- vector<int> ans;
- while(j){
- ans.pb(j);
- j = prv[j];
- }
- reverse(all(ans));
- printf("%d\n", ans.size());
- for(int i = 0; i < ans.size(); i++){
- if(i) printf(" ");
- printf("%d", ans[i]);
- }
- printf("\n");
- }
- int main () {
- freopen("subsequence.in", "r", stdin);
- freopen("subsequence.out", "w", stdout);
- int t=1;
- //scanf("%d", &t);
- for(int i=1; i <= t; i++){
- //printf("Case #%d\n", i);
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement