Submission #724346

#	Time	Username	Problem	Language	Result	Execution time	Memory
724346		nishkarsh	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	1 ms	340 KiB

subsequence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2;
const int middle = 1<<N;
int ones[middle];
int dp[middle][middle][N+1];
int main(){
	for(int i = 0; i < 1<<(N-1); ones[(i<<1)+1]++, i++) ones[(i<<1)+1] = ones[i<<1] = ones[i];
	int n;
	cin >> n;
	int a[n],k[n],siz[n],link[n];
	fill(link,link+n,-1);
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) cin >> k[i];
	int ans = 0, ind = 0;
	for(int i = 0; i < middle; i++) for(int j = 0; j < middle; j++) for(int m = 0; m <= N; m++) dp[i][j][m] = -1;
	for(int i = 0; i < n; i++){
		siz[i] = 0;
		for(int j = 0; j < middle; j++){
			if((k[i] < ones[(a[i]>>N) & j]) || (k[i] - ones[(a[i]>>N) & j] > N)) continue;
			int *ptr = &dp[j][a[i]&(middle-1)][k[i] - ones[(a[i]>>N) & j]];
			if(*ptr != -1) if(siz[*ptr] > siz[i]) siz[i]=siz[*ptr],link[i]=*ptr;
		}
		siz[i]++;
		for(int j = 0; j < middle; j++){
			int *ptr = &dp[a[i]>>N][j][ones[a[i]&j]];
			if((*ptr == -1) || (siz[*ptr] < siz[i])) *ptr=i;
		}
		if(ans < siz[i]){
			ans = siz[i];
			ind = i;
		}
		// for(int i = 0; i < middle; i++) for(int j = 0; j < middle; j++) for(int m = 0; m <= N; m++) cout << i << " " << j << " " << m << " " << dp[i][j][m] << "\n";
		// cout << i << " " << siz[i] << "\n";
	}
	cout << ans << "\n";
	vector<int> nums;
	while(ind >= 0){
		nums.push_back(ind);
		ind = link[ind];
	}
	reverse(nums.begin(),nums.end());
	for(int i : nums) cout << i+1 << " ";
	return 0;
}

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