Submission #236487

#	Time	Username	Problem	Language	Result	Execution time	Memory
236487		maskoff	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	5 ms	384 KiB

subsequence

#include <bits/stdc++.h>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define sc second
#define fr first
 
#define pb push_back
#define mp make_pair

#define pss pair<line*, line*>
 
using namespace std;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
                                 
const ll inf = 1e18;
const int MOD = 1e9 + 7;

const int dx[] = {-1, +1, -2, +2, -2, +2, -1, +1};
const int dy[] = {-2, -2, -1, -1, +1, +1, +2, +2};

int const N = 6e5;

int get (int x) {
	int res = 0;
 	while (x > 0) {
 		if (x % 2 == 1)
 			res++;
 		x /= 2;
 	}
 	return res;
}

int dp[N], p[N];

int main() {                
#ifdef Mask                                                         
  freopen(".in", 	"r", stdin);
  freopen(".out", "w", stdout);  
#endif
	ios_base :: sync_with_stdio(false);               
  cin.tie(nullptr); 	
  int n;
  cin >> n;
  int k[n + 1], a[n + 1];
  for (int i = 1; i <= n; i++)
  	cin >> a[i];
  for (int i = 1; i <= n; i++)
  	cin >> k[i];
  int ans[n + 1][n + 1];
  for (int i = 1; i <= n; i++)
  	for (int j = 1; j < i; j++) {
  		ans[i][j] = (a[i] & a[j]);
  		ans[i][j] = get(ans[i][j]);
  	}
  dp[1] = 1;
 	for (int i = 2; i <= n; i++)
 		for (int j = 1; j < i; j++) {
 			if (ans[i][j] == k[i]) {
 		 		if (dp[j] + 1 > dp[i]) {
 		 		 	dp[i] = dp[j] + 1;
 		 		 	p[i] = j;
 		 		}
 		 	}
 		}
 	int mx = 0;
 	int cur_i = 0;
 	for (int i = 1; i <= n; i++) 
 		if (dp[i] > mx) {
 			cur_i = i;
 			mx = dp[i];
 		}
 	vector<int> all;
 	while (cur_i >= 1) {
 		all.pb(cur_i);
 		cur_i = p[cur_i];
 	}
 	sort(all(all));
 	cout << all.size() << endl;    
 	assert((int)all.size() == mx);	
 	for (int to : all)
 		cout << to << " ";
	return 0;
}

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