Submission #92285

#	Time	Username	Problem	Language	Result	Execution time	Memory
92285		davitmarg	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	2 ms	376 KiB

subsequence

/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <cassert>
#include <fstream>  
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;

int bitCount(LL x)
{
	int res=0;
	while (x)
	{
		res += x % 2;
		x /= 2;
	}
	return res;
}

int bitCount(LL a,LL b)
{
	return bitCount(a&b);
}

int n, k[100005],dp[100005],nxt[100005],last[(1<<8)],mx;
LL a[100005];
bool p23;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (a[i] > (1 << 8))
			p23=1;
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> k[i];
		if (k[i] > 8)
			p23 = 1;
	}
	if (p23 && 0)
	{
		dp[n] = 1;
		for (int i = n - 1; i >= 1; i--)
		{
			dp[i] = 1;
			for (int j = i + 1; j <= n; j++)
				if (bitCount(a[i], a[j]) == k[j] && dp[i] < 1 + dp[j])
				{
					dp[i] = 1 + dp[j];
					nxt[i] = j;
				}
		}


		for (int i = 1; i <= n; i++)
			mx = max(dp[i], mx);
		cout << mx << endl;
		for (int i = 1; i <= n; i++)
			if (dp[i] == mx)
			{
				while (i)
				{
					cout << i << " ";
					i = nxt[i];
				}
				break;
			}
		cout << endl;

	}
	else
	{
		reverse(a,a+n);
		reverse(k,k+n);
		dp[n] = 1;
		last[a[n]] = n;
		for (int i = n - 1; i >= 1; i--)
		{
			dp[i] = 1;
			for (int j = 0; j <= (1<<8); j++)
				if (last[j] && bitCount(a[i], j) == k[i] && dp[i] < 1 + dp[last[j]])
				{
					dp[i] = 1 + dp[last[j]];
					nxt[i] = last[j];
				}
			last[a[i]] = i;
		}


		for (int i = 1; i <= n; i++)
			mx = max(dp[i], mx);
		cout << mx << endl;
		vector<int> o;
		for (int i = 1; i <= n; i++)
			if (dp[i] == mx)
			{
				while (i)
				{
					o.PB(n-i+1);
					i = nxt[i];
				}
				break;
			}
		sort(o.begin(), o.begin()+mx);
		for (int i = 0; i < mx; i++)
			cout << o[i] << " ";
		cout << endl;

	}
	return 0;
}

/*


5
5 3 5 3 5 
10 1 20 1 20

4
1 2 3 4 
10 0 1 0

*/

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:103:15: warning: iteration 256 invokes undefined behavior [-Waggressive-loop-optimizations]
     if (last[j] && bitCount(a[i], j) == k[i] && dp[i] < 1 + dp[last[j]])
         ~~~~~~^
subsequence.cpp:102:22: note: within this loop
    for (int j = 0; j <= (1<<8); j++)
                    ~~^~~~~~~~~

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