Submission #299390

#	Time	Username	Problem	Language	Result	Execution time	Memory
299390		luciocf	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5586 ms	93520 KiB

subsequence

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e5+10;

int n;
int a[maxn], b[maxn];

int dp[maxn], ant[maxn];
pii best[1<<10][1<<10][11];

void print(int ans)
{
	printf("%d\n", ans);

	int at;
	for (int i = 1; i <= n; i++)
		if (dp[i] == ans)
			at = i;

	vector<int> out;

	while (at)
	{
		out.push_back(at);
		at = ant[at];
	}

	reverse(out.begin(), out.end());

	for (auto x: out)
		printf("%d ", x);
	printf("\n");
}

int main(void)
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	for (int i = 1; i <= n; i++)
		scanf("%d", &b[i]);

	int ans = 0;

	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1, ant[i] = 0;

		int half1 = 0, half2 = 0;

		for (int j = 0; j < 10; j++)
		{
			if (a[i]&(1<<j))
				half1 += (1<<j);

			if (a[i]&(1<<(j+10)))
				half2 += (1<<j);
		}

		for (int mask = 0; mask < (1<<10); mask++)
		{
			int x = __builtin_popcount(half1&mask);

			if (b[i] >= x && b[i]-x <= 10)
			{
				if (1 + best[mask][half2][b[i]-x].ff > dp[i])
				{
					dp[i] = 1 + best[mask][half2][b[i]-x].ff;

					ant[i] = best[mask][half2][b[i]-x].ss;
				}
			}
		}

		for (int mask = 0; mask < (1<<10); mask++)
		{
			int x = __builtin_popcount(half2&mask);

			if (dp[i] > best[half1][mask][x].ff)
				best[half1][mask][x] = {dp[i], i};
		}

		ans = max(ans, dp[i]);
	}

	print(ans);
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
subsequence.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |   scanf("%d", &b[i]);
      |   ~~~~~^~~~~~~~~~~~~

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