Submission #768185

#	Time	Username	Problem	Language	Result	Execution time	Memory
768185		rainboy	Longest beautiful sequence (IZhO17_subsequence)	C11	100 / 100	2331 ms	51860 KiB

subsequence

#include <stdio.h>

#define N	100000
#define L	20

int max(int a, int b) { return a > b ? a : b; }

int cnt[1 << L];

void init() {
	int b;

	for (b = 1; b < 1 << L; b++)
		cnt[b] = cnt[b & b - 1] + 1;
}

int main() {
	static int aa[N], cc[N], dp[N], dq[1 << L][L / 2 + 1];
	static char used[N];
	int n, i, i_, j, a, a_, b, c;

	init();
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &cc[i]);
	i_ = -1;
	for (i = 0; i < n; i++) {
		for (b = 0; b < 1 << L / 2; b++) {
			c = cc[i] - cnt[aa[i] & b];
			if (c >= 0 && c <= L / 2)
				dp[i] = max(dp[i], dq[aa[i] & ~((1 << L / 2) - 1) | b][c]);
		}
		dp[i]++;
		for (a = 0; a < 1 << L - L / 2; a++) {
			c = cnt[aa[i] >> L / 2 & a];
			a_ = a << L / 2 | aa[i] & (1 << L / 2) - 1;
			dq[a_][c] = max(dq[a_][c], dp[i]);
		}
		if (i_ == -1 || dp[i_] < dp[i])
			i_ = i;
	}
	used[j = i_] = 1;
	for (i = j - 1; i >= 0; i--)
		if (cnt[aa[i] & aa[j]] == cc[j] && dp[j] == dp[i] + 1)
			used[j = i] = 1;
	printf("%d\n", dp[i_]);
	for (i = 0; i < n; i++)
		if (used[i])
			printf("%d ", i + 1);
	printf("\n");
	return 0;
}

Compilation message (stderr)

subsequence.c: In function 'init':
subsequence.c:14:22: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |   cnt[b] = cnt[b & b - 1] + 1;
      |                    ~~^~~
subsequence.c: In function 'main':
subsequence.c:33:33: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   33 |     dp[i] = max(dp[i], dq[aa[i] & ~((1 << L / 2) - 1) | b][c]);
      |                           ~~~~~~^~~~~~~~~~~~~~~~~~~~~
subsequence.c:36:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |   for (a = 0; a < 1 << L - L / 2; a++) {
      |                     ^~
subsequence.c:38:28: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   38 |    a_ = a << L / 2 | aa[i] & (1 << L / 2) - 1;
      |                            ^
subsequence.c:38:28: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   38 |    a_ = a << L / 2 | aa[i] & (1 << L / 2) - 1;
      |                      ~~~~~~^~~~~~~~~~~~~~~~~~
subsequence.c:23:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
subsequence.c:25:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
subsequence.c:27:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%d", &cc[i]);
      |   ^~~~~~~~~~~~~~~~~~~
subsequence.c:44:15: warning: writing 1 byte into a region of size 0 [-Wstringop-overflow=]
   44 |  used[j = i_] = 1;
      |  ~~~~~~~~~~~~~^~~
subsequence.c:19:14: note: at offset -1 to object 'used' with size 100000 declared here
   19 |  static char used[N];
      |              ^~~~

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