Submission #35049

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

subsequence

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int maxn = (int)(1e5 + 111);

int n, a[maxn], k[maxn], dp[maxn], p[maxn], cnt[(1 << 20) + 111];
int b[maxn], m;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);		
	for (int i = 0; i < n; ++i)
		scanf("%d", &k[i]);

	for (int i = 0; i < n; ++i) {
		dp[i] = 1;
		p[i] = -1;
	}

	for(int i = 0; i < (1<<20); i++)
		cnt[i] = __builtin_popcount(i);

	int q = 0, ans = 0;

	for (int i = 0; i < n; ++i)
	for (int j = 0; j < i; ++j)
		if (cnt[a[j] & a[i]] == k[i] && dp[i] < dp[j] + 1) {
			dp[i] = dp[j] + 1;
			p[i] = j;
		}

	for (int i = 0; i < n; ++i)
		if (dp[i] > ans) {
			ans = dp[i];
			q = i;
		}


	while (q != -1) {
		b[m++] = q + 1;
		q = p[q]; 	
	}

	reverse(b, b + m);

	printf("%d\n", m);
	for (int i = 0; i < m; ++i)
			printf("%d ", b[i]);

	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:20:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
subsequence.cpp:22:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);  
                     ^
subsequence.cpp:24:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k[i]);
                     ^

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