Submission #887814

#TimeUsernameProblemLanguageResultExecution timeMemory
887814vjudge1Longest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6052 ms166200 KiB
#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 1e5 + 66;
 
const int LOG = 20;
const int HALF = LOG >> 1;
 
pair<int,int>dp[N],vals[1<<HALF][1<<HALF][LOG];
 
int a[N], k[N];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; ++ i) cin >> a[i];
	for (int i = 1 ; i <= n ; ++ i) cin >> k[i];
	for (int i = 1 ; i <= n ; ++ i) {
		int m1 = (a[i] & ((1 << HALF) - 1));
		int m2 = (a[i] >> HALF);
		for (int m2q = 0 ; m2q < (1 << HALF) ; ++ m2q) {
			int k2q = __builtin_popcount(m2 & m2q);
			int need = k[i] - k2q;
			if (need >= 0 && need < LOG) {
				dp[i] = max(dp[i], vals[m1][m2q][need]);
			}
		}
		dp[i].first++;
		pair<int,int>rel = {dp[i].first, i};
		for (int m1q = 0 ; m1q < (1 << HALF) ; ++ m1q) {
			int k1q = __builtin_popcount(m1q & m1);
			vals[m1q][m2][k1q] = max(vals[m1q][m2][k1q], rel);
		}
		cerr << dp[i].first << " " << dp[i].second << endl;
	}
	int x = max_element(dp + 1, dp + 1 + n) - dp;
	cout << dp[x].first << "\n";
	vector<int>ans;
	while (x != 0) {
		ans.emplace_back(x);
		x = dp[x].second;
	}
	for (int i = (int)ans.size() - 1 ; i >= 0 ; -- i) cout << ans[i] << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...