Submission #934464

#	Time	Username	Problem	Language	Result	Execution time	Memory
934464		parsadox2	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	1682 ms	3208 KiB

subsequence

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
#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;
int n , a[N] , b[N] , dp[N];

inline int pop_count(int v){
	v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
	return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
}

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];
	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 ,pop_count((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 && pop_count(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;
}

Compilation message (stderr)

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

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