Submission #883601

#	Time	Username	Problem	Language	Result	Execution time	Memory
883601		NintsiChkhaidze	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2021 ms	104908 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 + 3;

int a[N],k[N],last[N];
int d[1026][1026][12],id[1026][1026][12];
int blt[1026][1026];

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	// freopen("subsequence.in", "r", stdin);
	// freopen("subsequence.out", "w", stdout);

	int n,ans = 0;
	cin>>n;

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

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

	for (int x=0;x<1024;x++)
		for (int y=0;y<1024;y++)
			blt[x][y] = __builtin_popcount(x & y);
		
	int idx = 0,x1,x2,c1,c2;
	for (int i = 1; i <= n; i++){
		
		x1=x2=0;
		int dp = 1;
		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 < 1024; y1++){
			c2 = k[i] - blt[x1][y1];
			if (c2 >= 0 && c2 <= 10) {
				int nw = d[y1][x2][c2];
				if (nw > dp){
					dp = nw;
					last[i] = id[y1][x2][c2];
				}
			}
		}

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

		if (dp > ans){
			ans = dp;
			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] <<" ";
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:37:20: warning: unused variable 'c1' [-Wunused-variable]
   37 |  int idx = 0,x1,x2,c1,c2;
      |                    ^~

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