Submission #884496

#	Time	Username	Problem	Language	Result	Execution time	Memory
884496		tsumondai	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	6035 ms	262144 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e6 + 5, B = 1024;

const int oo = 1e9, mod = 1e9 + 7;
int n, a[N], k[N], p[N], dp[21][B][B], g[21][B][B];
array<int, 2> res;

signed process() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	foru(i, 0, n - 1) cin >> a[i];

	foru(i, 0, n - 1) {
		cin >> k[i];
		int curr = 1, req, x = (a[i] & (B - 1)), r = (a[i] ^ x) >> 10;
		p[i] = -1;

		foru(l, 0, B - 1) {
			req = k[i] - __builtin_popcount(l & x);
			if (0 <= req && curr <= dp[req][r][l]) {
				curr = dp[req][r][l] + 1;
				p[i] = g[req][r][l];
			}
		}

		foru(j, 0, B - 1) {
			req = __builtin_popcount(j & r);
			if (dp[req][j][x] < curr) {
				dp[req][j][x] = curr;
				g[req][j][x] = i;
			}
		}

		res = max(res, {curr, i});
	}
	cout << res[0] << '\n';
	int ans[res[0]];
	foru(i, 0, res[0] - 1) {
		ans[i] = res[1];
		res[1] = p[res[1]];
	}
	ford(i, res[0]-1, 0) cout << ans[i] + 1 << ' ';
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	//freopen(".inp", "r", stdin);
	//freopen(".out", "w", stdout);
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

// dont stop

Compilation message (stderr)

subsequence.cpp: In function 'int process()':
subsequence.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
   57 | }
      | ^

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