Submission #36145

#	Time	Username	Problem	Language	Result	Execution time	Memory
36145		user202729	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6000 ms	3192 KiB

subsequence

#include <iostream>
#include <vector>
#include <algorithm>

#pragma

uint32_t popcount(uint32_t v) {
	v = v - ((v >> 1) & 0x55555555u);
	v = (v & 0x33333333u) + ((v >> 2u) & 0x33333333u);
	return (((v + (v >> 4u)) & 0xF0F0F0Fu) * 0x1010101u) >> 24u;
}

int main() {
	size_t n; std::cin >> n;
	std::vector<uint32_t> a (n), k (n);
	for (uint32_t& ai : a) std::cin >> ai;
	for (uint32_t& ki : k) std::cin >> ki;

	/// dp[i] = length of longest valid sequence ends at (i)
    std::vector<int> dp (n, 1);

    for (size_t i = 1; i < n; ++i) {

		uint32_t ai = a[i], ki = k[i];
		if (popcount(ai) < ki) continue; // failed, dp[i] == 1

		int dpi = 0;

		for (size_t prev = i; prev --> 0;) {

			if (popcount(a[prev] & ai) == ki) {
				dpi = std::max(dpi, dp[prev]);
			}
		}

		dp[i] = ++dpi;
    }

    auto it = std::max_element(dp.begin(), dp.end());
    size_t index = size_t(it - dp.begin());
    int value = *it; --value;

    std::vector<size_t> rev_indices = {index};
    while (value != 0) {
		index = rev_indices.back();
		int dp_last_exp = dp[index] - 1;

		size_t last_index;
		for (last_index = index; last_index --> 0;)
			if (dp_last_exp == dp[last_index] && popcount(a[last_index] & a[index]) == k[index]) break;

		rev_indices.push_back(last_index);
		--value;
    }

    std::cout << *it << '\n';
    for (size_t i = rev_indices.size(); i --> 0;) std::cout << -~rev_indices[i] << ' ';
}

// 4 1 2 3 4 10 0 1 0

Compilation message (stderr)

subsequence.cpp:5:0: warning: ignoring #pragma   [-Wunknown-pragmas]
 #pragma
 ^

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