Submission #650010

#	Time	Username	Problem	Language	Result	Execution time	Memory
650010		ymm	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3661 ms	2416 KiB

subsequence

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
int dp[N], pre[N];
int a[N], k[N];
int n;

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
int get(int l, int r, int x, int k)
{
	#define MAX(a, b) ((a)>(b)?(a):(b))
	#define POPCNT(x) do { \
		x -= (x>>1) & 0x55'55'55'55;\
		x = (x & 0x33'33'33'33) + ((x>>2) & 0x33'33'33'33);\
		x = (x + (x>>4)) & 0x0f'0f'0f'0f;\
		x = (x + (x >> 8) + (x >> 16)) & 0xff;\
	} while(0)
	int ans = 0;
	Loop (j,l,r) {
		int tmp = a[j] & x;
		POPCNT(tmp);
		tmp = -(tmp == k);
		tmp &= dp[j];
		ans = MAX(ans, tmp);
	}
	return ans;
	#undef MAX
	#undef POPCNT
}

void up(int i, int x, int k)
{
	int ans = 0, ansi = -1;
	const int S = 4096;
	for (int l = 0; l < i; l += S) {
		int r = min(l+S, i);
		int tmp = get(l, r, x, k);
		if (tmp > ans) {
			ans = tmp;
			ansi = l;
		}
	}
	if (ansi >= 0) {
		Loop (j,ansi,ansi+S) {
			if (  dp[j] == ans
			    && __builtin_popcount(a[j]&x) == k) {
				ansi = j;
				break;
			}
		}
	}
	pre[i] = ansi;
	dp[i] = ans+1;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n)
		cin >> a[i];
	Loop (i,0,n)
		cin >> k[i];
	Loop (i,0,n)
		up(i, a[i], k[i]);
	int i = 0;
	Loop (j,0,n) {
		if (dp[j] > dp[i])
			i = j;
	}
	vector<int> vec;
	while (i != -1) {
		vec.push_back(i);
		i = pre[i];
	}
	reverse(vec.begin(), vec.end());
	cout << vec.size() << '\n';
	for (int v : vec)
		cout << v+1 << ' ';
	cout << '\n';
}

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