Submission #888409

#	Time	Username	Problem	Language	Result	Execution time	Memory
888409		pcc	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	83 ms	2908 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;
int n;
int arr[mxn],brr[mxn];

namespace small{
	pii dp[mxn];
	void GO(){
		dp[0] = make_pair(0,0);
		for(int i = 1;i<=n;i++){
			dp[i] = make_pair(1,0);
			for(int j = i-1;j>=0;j--){
				if(__builtin_popcount(arr[j]&arr[i]) == brr[i]){
					dp[i] = max(dp[i],{dp[j].fs+1,j});
				}
			}
		}
		int now= max_element(dp,dp+n+1)-dp;
		int cnt = dp[now].fs;
		vector<int> v;
		while(now){
			v.push_back(now);
			now = dp[now].sc;
		}
		reverse(v.begin(),v.end());
		cout<<cnt<<'\n';
		for(auto &i:v)cout<<i<<' ';
		return;
	}
}

namespace big{
	int pre[mxn];
	vector<int> v;
	pii dp[1<<8];
	void GO(){
		for(int i = 1;i<=n;i++){
			pii big = {0,0};
			for(int j = 0;j<(1<<8);j++){
				if(__builtin_popcount(arr[i]&j) != brr[i])continue;
				big = max(big,dp[j]);
			}
			pre[i] = big.sc;
			dp[arr[i]] = max(dp[arr[i]],{big.fs+1,i});
		}
		int now = max_element(dp,dp+(1<<8))->sc;
		while(now){
			v.push_back(now);
			now = pre[now];
		}
		reverse(v.begin(),v.end());
		cout<<v.size()<<'\n';
		for(auto &i:v)cout<<i<<' ';
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)cin>>arr[i];
	for(int i = 1;i<=n;i++)cin>>brr[i];
	if(n<=5050)small::GO();
	else big::GO();
}

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