Submission #1269120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269120		lmduc270410	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	4254 ms	8172 KiB

subsequence

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,fma,sse,sse2,sse3,sse4.1,sse4.2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
const int N = 1e5 + 5, M = 2e6 + 5;
const int BUF_SZ = 1 << 15;

inline namespace Input {
char buf[BUF_SZ];
int pos;
int len;
char next_char() {
	if (pos == len) {
		pos = 0;
		len = (int)fread(buf, 1, BUF_SZ, stdin);
		if (!len) { return EOF; }
	}
	return buf[pos++];
}

int read_int() {
	int x;
	char ch;
	int sgn = 1;
	while (!isdigit(ch = next_char())) {
		if (ch == '-') { sgn *= -1; }
	}
	x = ch - '0';
	while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
	return x * sgn;
}
}  // namespace Input
inline namespace Output {
char buf[BUF_SZ];
int pos;

void flush_out() {
	fwrite(buf, 1, pos, stdout);
	pos = 0;
}

void write_char(char c) {
	if (pos == BUF_SZ) { flush_out(); }
	buf[pos++] = c;
}

void write_int(int x) {
	static char num_buf[100];
	if (x < 0) {
		write_char('-');
		x *= -1;
	}
	int len = 0;
	for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); }
	write_char((char)('0' + x));
	while (len) { write_char(num_buf[--len]); }
	// write_char(' ');
}

// auto-flush output when program exits
void init_output() { assert(atexit(flush_out) == 0); }
}  // namespace Output

int n, a[N], k[N], pcnt[M];
pii dp[N];
int idk[N];

inline pii fmax(const pii &a, const pii &b) {
    bool take_a = (a.first > b.first) || 
                  (a.first == b.first && a.second > b.second);
    return take_a ? a : b;
}

map<int, vector<int>, greater<int>> mp;

inline void solve(){
	
	cin>>n;
	for(int i = 1; i <= n; i++) a[i] = read_int();
	for(int i = 1; i <= n; i++) k[i] = read_int();
	for(int i = 1; i <= (1 << 20); i++) pcnt[i] = __builtin_popcount(i);

	pii ans = {0, 0};
	for(int i = 1; i <= n; i++){
		dp[i] = {1, i};
		int cb = pcnt[a[i]];
		if(cb < k[i]){
			ans = max(ans, {1, i});
			mp[2].push_back(i);
			continue;
		}
		for(auto g : mp){
			for(auto j : g.se){
				if(pcnt[(a[j] & a[i])] == k[i]){
					dp[i] = {g.fi, j};
					break;
				}
			}
			if(dp[i].se != i) break;
		}
		ans = max(ans, {dp[i].fi, i});
		mp[dp[i].fi + 1].push_back(i);
	}

	// for(int i = 1; i <= n; i++) cout<<"!!! "<<dp[i].fi<<" "<<dp[i].se<<'\n';

	write_int(ans.fi);
	write_char('\n');
	int m = 0, cur = ans.se;
	while(dp[cur].se != cur){
		idk[++m] = cur;
		cur = dp[cur].se;
	}
	idk[++m] = cur;
	for(int i = m; i >= 1; i--) write_int(idk[i]), write_char(' ');
}

signed main(){
	
	// freopen(".inp", "r", stdin);
	// freopen(".out", "w", stdout);

	// ios_base::sync_with_stdio(0);
	// cin.tie(0); cout.tie(0);

	init_output();
	solve();
}

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