제출 #1099999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099999		Muhammet	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	6492 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

int n, m[1<<20], p[1<<20], in[1<<20];

vector <int> a, k;

int bitcount(int x){
	int ans = 0;
	while(x){
		ans += (x%2);
		x /= 2;
	}
	return ans;
}

int f(int x, int k2, int ind){
	int ans = 0;
	for(int i = 0; i <= (1<<8); i++){
		// cout << x << ' ' << i << ' ' << (x&i) << ' ' << bitcount(x&i) << '\n';
		if(bitcount(x&i) == k2){
			// cout << y << ' ' << i << ' ' << m[i] << '\n';
			if(ans < m[i] and in[i] != -1){
				p[ind] = in[i];
			}
			ans = max(ans,m[i]);
		}
	}
	return ans+1;
}

int main(){
	cin >> n;
	a.resize(n+1);
	k.resize(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		p[i] = -1;
	}
	for(int i = 1; i <= n; i++){
		cin >> k[i];
	}
	int ans = 0, ind = 1;
	for(int i = 1; i <= n; i++){
		// cout << i << ' ' << k[i] << '\n';
		m[a[i]] = (f(a[i],k[i],i));
		if(m[a[i]] > ans){
			ind = i;
		}
		ans = max(ans,m[a[i]]);
		in[a[i]] = i;
		// cout << i << ' ' << m[a[i]] << '\n';
	}
	cout << ans << '\n';
	vector <int> v;
	while(ind > 0){
		v.push_back(ind);
		ind = p[ind];
	}
	reverse(v.begin(), v.end());
	for(auto i : v){
		cout << i << ' ';
	}
}

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