Submission #1231628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231628		kaiboy	Sequence (BOI14_sequence)	C++20	42 / 100	1095 ms	584 KiB

sequence

#include <algorithm>
#include <iostream>

using namespace std;

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

int dd[N];

int next(int d, int d_) {
	do
		d++;
	while (d == d_);
	return d;
}

bool check(int a, int d) {
	for ( ; a; a /= 10)
		if (a % 10 == d)
			return true;
	return false;
}

bool check_(int a, int d) {
	return a < A / 10 && !d || check(a, d);
}

int main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> dd[i];
	bool eq = true;
	for (int i = 1; i < n; i++)
		if (dd[i] != dd[0]) {
			eq = false;
			break;
		}
	if (eq) {
		int d_ = dd[0];
		for (int a = 1; ; a++) {
			int k = 0;
			for (int b = a; b; b /= 10)
				dd[k++] = b % 10;
			int b = 0, h = k - 1;
			while (h >= 0 && dd[h] != d_)
				b = b * 10 + dd[h--];
			if (h >= 0) {
				int d = next(dd[h], d_);
				if (d < 10) {
					b = b * 10 + d;
					d = next(-1, d_);
					for (h--; h >= 0; h--)
						b = b * 10 + d;
				} else {
					do
						h++, b /= 10;
					while (h < k && next(dd[h], d_) == 10);
					d = next(-1, d_);
					b = b * 10 + (h < k ? next(dd[h], d_) : d);
					for (h--; h >= 0; h--)
						b = b * 10 + d;
				}
			}
			if (b - a >= n) {
				cout << a << '\n';
				return 0;
			}
		}
		return 0;
	}
	for (int a = 1; a < A; a++) {
		bool yes = true;
		for (int i = 0; i < n; i++)
			if (!check(a + i, dd[i])) {
				yes = false;
				break;
			}
		if (yes) {
			cout << a << '\n';
			return 0;
		}
	}
	long long ans = INF;
	for (int a = 0; a < A - 1000; a++) {
		int b = 0;
		for (int i = 0; i < n; i++)
			if (!check_(a + i, dd[i]))
				b |= 1 << dd[i];
		if (!(b >> 1))
			b |= 1 << 1;
		long long x = 0;
		for (int d = 1; d < 10; d++) {
			if (b >> d & 1)
				x = x * 10 + d;
			if (x && b & 1)
				x *= 10, b &= ~1;
		}
		x = x * A + a;
		ans = min(ans, x);
	}
	cout << ans << '\n';
	return 0;
}

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