Submission #934454

#TimeUsernameProblemLanguageResultExecution timeMemory
934454parsadox2Longest beautiful sequence (IZhO17_subsequence)C++14
40 / 100
6011 ms6908 KiB
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

#define MAX(a,b) ((a) > (b) ? (a) : (b)) 

using namespace std;

const int N = 1e5 + 10 , M = (1 << 20) + 10;
int n , a[N] , b[N] , dp[N] , cnt[M];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);   cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
		cin >> a[i];
	for(int i = 1 ; i <= n ; i++)
		cin >> b[i];
	for(int i = 1 ; i < M ; i++)
		cnt[i] = cnt[i >> 1] + (i & 1);
	int ans = 0 , las = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		int dard = 0;
		for(int j = 1 ; j < i ; j++)  
			dard = MAX(dard , __builtin_popcount((a[i] & a[j])) == b[i] ? dp[j] : 0);
		dp[i] = dard + 1;
		ans = max(ans , dp[i]);
		if(dp[i] == ans)
			las = i;
	}
	vector <int> res;
	res.push_back(las);
	for(int i = las - 1 ; i > 0 ; i--)
	{
		if(dp[i] == dp[las] - 1 && __builtin_popcount(a[las] & a[i]) == b[las])
		{
			res.push_back(i);
			las = i;
		}
	}
	cout << ans << '\n';
	for(int i = ans - 1 ; i > -1 ; i--)
		cout << res[i] << " ";
	cout << '\n';
	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...