Submission #167722

#TimeUsernameProblemLanguageResultExecution timeMemory
167722mosiashvililukaLongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
6 ms1272 KiB
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,f[100009],g[100009],dp[100009],nxt[100009],k[(1<<11)][(1<<11)][12],zx,xc,i,j,pas,pas2,cv,qw,we;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	qw=(1<<10);we=(1<<20);
	cin>>a;
	for(c=1; c<=a; c++) cin>>f[c];
	for(c=1; c<=a; c++) cin>>g[c];
	for(c=10; c<20; c++) xc+=(1<<c);
	for(c=0; c<10; c++) zx+=(1<<c);
	for(c=a; c>=1; c--){
		d=(f[c]&zx);
		e=(f[c]&xc);
		for(i=0; i<(1<<10); i++){
//		    cout<<dp[c]<<" "<<dp[k[i][e][__builtin_popcount((i&d))]+1]<<endl;
			if(dp[c]<dp[k[i][e][__builtin_popcount((i&d))]]+1){
/*			    if(c==1){
			        cout<<k[i][e][__builtin_popcount((i&d))]<<" "<<i<<" "<<e<<endl;
			    }*/
				nxt[c]=k[i][e][__builtin_popcount((i&d))];
				dp[c]=dp[k[i][e][__builtin_popcount((i&d))]]+1;
				if(pas<dp[c]){
					pas=dp[c];
					pas2=c;
				}
			}
		}
		for(i=0; i<we; i+=qw){
		    j=i/(1<<10);
			cv=__builtin_popcount((i&e));
			if(cv>g[c]) continue;
			if(dp[k[d][j][g[c]-cv]]<dp[c]){
//			    cout<<d<<" zx "<<i<<endl;
//			    if(d==16) cout<<i<<" d "<<dp[c]<<endl;
				k[d][j][g[c]-cv]=c;
/*				if(k[16][0][0]==2){
				    cout<<d<<" "<<i<<" "<<g[c]-cv<<endl;
				}*/
			}
		}
//		cout<<k[16][0][0]<<endl;
	}
	cout<<pas<<endl;
	c=pas2;
	while(c!=0){
		cout<<c<<" ";
		c=nxt[c];
	}
	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...