Submission #934703

#TimeUsernameProblemLanguageResultExecution timeMemory
934703amirhoseinfar1385Longest beautiful sequence (IZhO17_subsequence)C++17
7 / 100
293 ms262144 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxk=22;
int all[maxn],dp[(1<<12)][(1<<12)][maxk],n,allb[maxn],res[maxn];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	for(int i=1;i<=n;i++){
		cin>>allb[i];
	}
	for(int i=1;i<=n;i++){
		int first=(all[i]&((1<<11)-1));
		int second=(all[i]>>11);
		int mx=0,btf=0,bts=0;
		for(int j=0;j<(1<<11);j++){
			btf=__builtin_popcount(first&j);
			if(btf>allb[i]){
				continue;
			}
			mx=max(mx,dp[j][second][allb[i]-btf]);
		}
		res[i]=mx+1;
		for(int j=0;j<(1<<11);j++){
			bts=__builtin_popcount(second&j);
			dp[first][j][bts]=max(dp[first][j][bts],res[i]);
		}
	}
	vector<int>mainres;
	int mx=0,last=0;
	for(int i=1;i<=n;i++){
		if(res[i]>mx){
			last=i;
			mx=res[i];
		}
	}
	mainres.push_back(last);
	int f=last;
	while(res[last]!=1){
		f=last;
		for(int i=last-1;i>=1;i--){
			if(res[i]==res[last]-1&&__builtin_popcount(all[last]&all[i])==allb[last]){
				last=i;
				mainres.push_back(last);
				break;
			}
		}
		if(f==last){
			assert(0);
		}
	}
	reverse(mainres.begin(),mainres.end());
	int sz=mainres.size();
	cout<<sz<<"\n";
	for(auto x:mainres){
		cout<<x<<" ";
	}
	cout<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...