Submission #1235369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235369		kaiboy	Sequence (BOI14_sequence)	C++20	34 / 100	54 ms	840 KiB

sequence

// coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const       int   N = 100000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

long long solve(int *bb, int n, int n_, bool eof) {
	if (n == 1) {
		int b = bb[0];
		if (b == 1)
			b = 3;
		long long ans = 0;
		for (int d = 1; d < 10; d++)
			if (b >> d & 1)
				ans = ans * 10 + d;
		if (b & 1)
			ans *= 10;
		if (!ans && !eof)
			ans = 1;
		return ans;
	}
	if (eof && !bb[0]) {
		int m = (n + 9) / 10;
		int *cc = new int[m];
		for (int j = 0; j < m; j++)
			cc[j] = 0;
		for (int d = 1, j = 0, i = 1; i < n; i++) {
			int b = bb[i];
			if (b >> d & 1)
				b ^= 1 << d;
			cc[j] |= b;
			if (d < 9)
				d++;
			else
				d = 0, j++;
		}
		bool yes = !solve(cc, m, n, true);
		delete[] cc;
		if (yes)
			return 0;
	}
	long long ans = INF;
	for (int d_ = 0; d_ < 10; d_++) {
		if (n_ == 2 && d_ == 9)
			continue;
		int m = 1 + (n - (10 - d_) + 9) / 10;
		int *cc = new int[m];
		for (int j = 0; j < m; j++)
			cc[j] = 0;
		for (int d = d_, j = 0, i = 0; i < n; i++) {
			int b = bb[i];
			if (b >> d & 1)
				b ^= 1 << d;
			cc[j] |= b;
			if (d < 9)
				d++;
			else
				d = 0, j++;
		}
		ans = min(ans, solve(cc, m, n, d_) * 10 + d_);
		delete[] cc;
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	int *bb = new int[n];
	for (int i = 0; i < n; i++) {
		int d; cin >> d;
		bb[i] = 1 << d;
	}
	cout << solve(bb, n, 0, false) << '\n';
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 33
• Subtask 3: 25 / 25
• Subtask 4: 0 / 33