Submission #92063

#	Time	Username	Problem	Language	Result	Execution time	Memory
92063		emil_physmath	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	2 ms	504 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], maxdp[1<<9]; // maxdp[k][i]

void SubTaskTwo(int n);
void SubTaskThree(int n);
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);
	/*
	if (n<=5000)
		SubTaskTwo(n);
	else
	*/
		SubTaskThree(n);

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

void SubTaskTwo(int n)
{
	dp[0]=1;
	prevNum[0]=-1;
	for (int i=1; i<n; i++)
	{
		dp[i]=1;
		prevNum[i]=-1;
		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<<'\n';
}

void SubTaskThree(int n)
{
	for (int j=0; j<(1<<8); j++)
		maxdp[j]=-1;
	dp[0]=1;
	prevNum[0]=-1;
	maxdp[a[0]]=0;
	for (int i=1; i<n; i++)
	{
		if (a[i]>(1<<8) || a[0]>(1<<8))
			for(;;);
		dp[i]=1;
		prevNum[i]=-1;
		for (int j=0; j<(1<<8); j++)
			if (NumBits(a[i] & j)==k[i])
				if (maxdp[j]!=-1 && dp[maxdp[j]]+1>dp[i])
				{
					dp[i]=dp[maxdp[j]]+1;
					prevNum[i]=maxdp[j];
		if (maxdp[a[i]]==-1 || dp[i]>dp[maxdp[a[i]]])
			maxdp[a[i]]=i;
				}
		if (maxdp[a[i]]==-1 || dp[i]>dp[maxdp[a[i]]])
			maxdp[a[i]]=i;
	}
	int bestEnd=0;
	for (int i=1; i<n; i++)
		if (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())
	{
		printf("%d ", ans.top()+1);
		ans.pop();
	}
	cout<<'\n';
	/*
	cout<<"dp[0...n-1]\n";
	for (int i=0; i<n; i++)
		cout<<dp[i]<<' ';
	cout<<'\n';
	for (int i=0; i<n; i++)
		cout<<"maxdp["<<a[i]<<"] = "<<maxdp[a[i]]<<'\n';
	*/
}
/*
5
8 3 4 2 4
1 2 3 2 1
*/
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:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
   ~~~~~^~~~~~~~~~~
subsequence.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", k+i);
   ~~~~~^~~~~~~~~~~
subsequence.cpp: In function 'void SubTaskTwo(int)':
subsequence.cpp:48: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