Submission #92726

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

subsequence

#include <bits/stdc++.h>

#define F first
#define S second
#define Pb push_back

using namespace std;

int n,a[100005],k[100005],X,Ans;

pair < int , int > Dp[100005];

vector < int > ANS;

main ()
{
	cin>>n;
	
	for (int i=1; i<=n; i++)
		cin>>a[i];
	
	for (int i=1; i<=n; i++)
	{
		cin>>k[i];
		Dp[i].F=1;
	}
	
	for (int i=1; i<=n; i++)
	{
		for (int j=i-1; j>=1; j--)
			if (__builtin_popcount(a[j]&a[i])==k[i])
			{
				Dp[i].F=Dp[j].F+1;
				Dp[i].S=j;
				break;
			}
		
		Ans=max(Ans,Dp[i].F);
	}
	
	cout<<Ans<<endl;
	
	for (int i=n; i>=1; i--)
		if (Ans==Dp[i].F) X=i;
				
	while (Dp[X].F!=1)
	{
		ANS.Pb(X);
		X=Dp[X].S;
	}
	
	ANS.Pb(X);
	
	reverse(ANS.begin(),ANS.end());
	
	for (int i=0; i<ANS.size(); i++)
		cout<<ANS[i]<<" ";
}
/*

4
1 2 3 4
10 0 1 0

2
8 9
20 0

5
5 3 5 3 5
10 1 20 1 20

*/

Compilation message (stderr)

subsequence.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ANS.size(); i++)
                ~^~~~~~~~~~~

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