제출 #92045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92045		emil_physmath	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	685 ms	263168 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)+5]; // 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<<9); j++)
		maxdp[j]=-1;
	dp[0]=1;
	prevNum[0]=-1;
	maxdp[a[0]]=0;
	for (int i=1; i<n; i++)
	{
		dp[i]=1;
		prevNum[i]=-1;
		if (maxdp[a[i]]==-1 || dp[i]>dp[maxdp[a[i]]])
			maxdp[a[i]]=i;
		for (int j=0; j<(1<<9); 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;
				}
	}
	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())
	{
		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';
	*/
}
 
int NumBits(int n)
{
	int res=0;
	while (n)
	{
		if (n & 1)
			res++;
		n>>=1;
	}
	return res;
}

컴파일 시 표준 에러 (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:46:6: warning: 'bestEnd' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int bestEnd;
      ^~~~~~~
subsequence.cpp: In function 'void SubTaskThree(int)':
subsequence.cpp:90:6: warning: 'bestEnd' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int bestEnd;
      ^~~~~~~

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