Submission #883598

#	Time	Username	Problem	Language	Result	Execution time	Memory
883598		NintsiChkhaidze	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4340 ms	110480 KiB

subsequence

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define pii pair<int,int>
#define ll long long
// #define int ll
using namespace std;

const int N = 1e5 + 5;

int a[N],dp[N],k[N],last[N];
int d[1027][1027][13],id[1027][1027][13];

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n,ans = 0;
	cin>>n;

	for (int i = 1; i <= n; i++)
		cin >> a[i],dp[i] = 1;

	for (int i = 1; i <= n; i++)
		cin >> k[i];

	int idx = 0,x1,x2,c1,c2;
	for (int i = 1; i <= n; i++){
		
		x1=x2=0;
		for (int j = 0; j < 20; j++){
			int bt = (a[i] & (1<<j)) > 0;
			if (j < 10) x1 ^= (a[i] & (1<<j)); 
			else x2 ^= bt * (1<<(j - 10));
		}

		for (int y1 = 0; y1 < (1<<10); y1++){
			c1 = __builtin_popcount(x1&y1);
			c2 = k[i] - c1;
			if (c2 >= 0 && c2 <= 10) {
				int nw = d[y1][x2][c2];
				if (nw > dp[i]){
					dp[i] = nw;
					last[i] = id[y1][x2][c2];;
				}
			}
		}

		//update
		for (int y2 = 0; y2 < (1<<10); y2++){
			c2 = __builtin_popcount(x2&y2);
			if (d[x1][y2][c2] < dp[i] + 1){
				d[x1][y2][c2] = dp[i] + 1;
				id[x1][y2][c2] = i;
			}
		}

		if (dp[i] > ans){
			ans = dp[i];
			idx = i;
		}
	}

	cout<<ans<<endl;
	vector <int> vec;
	for (int i = 1; i <= ans; i++){
		vec.pb(idx);
		idx = last[idx];
	}

	for (int i = ans - 1; i >= 0;i--)
		cout << vec[i] <<" ";
}

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