Submission #1269349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269349		g4yuhg	Longest beautiful sequence (IZhO17_subsequence)	C++20	40 / 100	74 ms	1608 KiB

subsequence

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define MP make_pair
#define fi first
#define se second
#define TASK "subsequence"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 100005
#define LOG 19
#define endl '\n'
using namespace std;

bool ghuy4g;

ll n, a[N], k[N];

ll dp[N], ans, trace[N], f[N];

void sub1() {
	ll id = 0;
	for (int i = 1; i <= n; i ++) {
		dp[i] = 1;
		for (int j = i - 1; j >= 1; j --) {
			if (__builtin_popcount(a[i] & a[j]) == k[i]) {
				dp[i] = max(dp[i], dp[j] + 1);
				if (dp[i] == dp[j] + 1) {
					trace[i] = j;
				}
			}
		}
		if (ans < dp[i]) {
			ans = dp[i];
			id = i;
		}
	}
	cout << ans << endl;
	vector<ll> vt;
	while (true) {
		vt.push_back(id);
		id = trace[id];
		if (id == 0) break;
	}
	reverse(vt.begin(), vt.end());
	for (auto it : vt) cout << it << " ";
}

void sub2() {
	ll id = 0;
	for (int i = 1; i <= n; i ++) {
		ll res = 1;
		for (int mask = 0; mask < (1 << 8); mask ++) {
			if (dp[mask] == 0 || __builtin_popcount(mask & a[i]) != k[i]) continue;
			if (res < dp[mask] + 1) {
				res = dp[mask] + 1;
				trace[i] = f[mask];
			}
		}
		if (res > dp[a[i]]) {
			dp[a[i]] = res;
			f[a[i]] = i;
		}
		//cout << "old id " << id << endl;
		if (ans < res) {
			//cout << i << " " << ans << " | " << res << endl;
			ans = res;
			id = i;
			//cout << "newid " << id << endl;
		}
		//cout << ans << " " << res << " " << id << endl;
	}
	cout << ans << endl;
	vector<ll> vt;
	while (true) {
		vt.push_back(id);
		id = trace[id];
		if (id == 0) break;
	}
	reverse(vt.begin(), vt.end());
	for (auto it : vt) cout << it << " ";
}

bool klinh;

signed main(void) {
    start;
    faster;
	  
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i ++) {
		cin >> k[i];
	}
	if (n <= 5000) {
		sub1();
	}
	else {
		sub2();
	}
   	
    cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:9:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:88:5: note: in expansion of macro 'start'
   88 |     start;
      |     ^~~~~
subsequence.cpp:9:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:88:5: note: in expansion of macro 'start'
   88 |     start;
      |     ^~~~~

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