Submission #91128

#	Time	Username	Problem	Language	Result	Execution time	Memory
91128		emil_physmath	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	2 ms	700 KiB

subsequence

#include <iostream>
#include <stdio.h>
#include <stack>
using namespace std;
const int MAXN=100000+5;

int a[MAXN], k[MAXN], dp[MAXN], prevNum[MAXN];

int NumBits(int);
int main()
{
	int n;
	cin>>n;
	for (int i=0; i<n; i++)
		scanf("%d", a+i);
	for (int i=0; i<n; i++)
		scanf("%d", k+i);
	dp[0]=1;
	prevNum[0]=-1;
	for (int i=1; i<n; i++)
		for (int j=0; j<i; j++)
			if (NumBits(a[i] & a[j])==k[i])
				if (dp[j]+1>dp[i])
				{
					dp[i]=dp[j]+1;
					prevNum[i]=j;
				}
	int bestEnd;
	for (int i=0; i<n; i++)
		if (!i || dp[i]>dp[bestEnd])
			bestEnd=i;
	stack<int> ans;
	int curNum=bestEnd;
	ans.push(curNum);
	while (prevNum[curNum]!=-1)
	{
		curNum=prevNum[curNum];
		ans.push(curNum);
	}
	cout<<ans.size()<<'\n';
	while (!ans.empty())
	{
		cout<<ans.top()+1<<' ';
		ans.pop();
	}
	cout<<endl;

	char I;
	cin >> I;
	return 0;
}

int NumBits(int n)
{
	int res=0;
	while (n)
	{
		if (n & 1)
			res++;
		n>>=1;
	}
	return res;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
   ~~~~~^~~~~~~~~~~
subsequence.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", k+i);
   ~~~~~^~~~~~~~~~~
subsequence.cpp:28:6: warning: 'bestEnd' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int bestEnd;
      ^~~~~~~

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