Submission #934713

#	Time	Username	Problem	Language	Result	Execution time	Memory
934713		amirhoseinfar1385	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4655 ms	93296 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
const int maxn=100000+10,maxk=22;
int all[maxn],dp[(1<<10)][(1<<10)][maxk],n,allb[maxn],res[maxn];
 
inline int pop_count(int v){
	v = v - ((v >> 1) & 0x55555555);
	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
	return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
 

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<<10)-1));
		int second=(all[i]>>10);
		int mx=0,btf=0,bts=0;
		for(int j=0;j<(1<<10);j++){
			btf=pop_count(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<<10);j++){
			bts=pop_count(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&&pop_count(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";
}

Compilation message (stderr)

subsequence.cpp: In function 'int pop_count(int)':
subsequence.cpp:11:13: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   11 |  return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
      |           ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60