Submission #1134354

#TimeUsernameProblemLanguageResultExecution timeMemory
1134354Halym2007Longest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
2166 ms47372 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
#define sana __builtin_popcount
const int N = 2e5 + 5;
// dp[x][y][r]-da in sonky best index durya 
int ans[N], par[N], dp[1 << 10][1 << 10][11];
int a[N], k[N];
int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	int answer = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> k[i];
		int pre = a[i] >> 10, suf = a[i] & (1 << 10) - 1;
		// jogaby gozlemeli
		ans[i] = 1;
		for (int j = 0; j < (1 << 10); ++j) {
			int need = k[i] - sana (j & pre);
			if (need < 0 or need > 10) continue;
			if (ans[dp[j][suf][need]] + 1 > ans[i]) {
				par[i] = dp[j][suf][need];
				ans[i] = ans[dp[j][suf][need]] + 1;
			}
		}
		// jogaby updatelayas
		for (int j = 0; j < (1 << 10); ++j) {
			if (ans[dp[pre][j][sana (suf & j)]] < ans[i]) {
				dp[pre][j][sana (suf & j)] = i;
			}
		}
		if (ans[answer] <= ans[i]) {
			answer = i;
		}
	}
	cout << ans[answer] << "\n";
	vector <int> cyk;
	while (answer) {
		cyk.pb (answer);
		answer = par[answer];
	}
	reverse(cyk.begin(), cyk.end());
	for (int i : cyk) {
		cout << i << " ";
	}
	cout << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...