Submission #42374

#	Time	Username	Problem	Language	Result	Execution time	Memory
42374		Aidyn_A	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6061 ms	3756 KiB

subsequence

#include <stdio.h>
#include <bits/stdc++.h>			

#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = (int)1e6 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;

void megaRandom() {
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  srand(FOR);
}

int n, dp[N], pr[N];
int a[N], b[N];

int main() {
	megaRandom();
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++) cin >> b[i];
	int res = 0, res_p = -1;
	for(int i = 1; i <= n; i ++) {
		dp[i] = 1;
		for(int j = 0; j < i; j ++) {
			if(__builtin_popcount(a[j] & a[i]) == b[i] && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
				pr[i] = j;
			}
		}
		if(res < dp[i]) {
			res = dp[i], res_p = i;
		}
	}
	cout << res << "\n";
	vector<int> v;
	while(res_p > 0) {
		v.pb(res_p);//cout << res_p << ' ';
		res_p = pr[res_p];
	}
	reverse(all(v));
	for(auto aa : v)
		cout << aa << ' ';
	return 0;  
}

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