Submission #544613

#	Time	Username	Problem	Language	Result	Execution time	Memory
544613		rainboy	Sequence (BOI14_sequence)	C11	100 / 100	76 ms	9516 KiB

sequence

/* upsolve after reading analysis */
#include <stdio.h>
#include <stdlib.h>

#define N	100000
#define L	5	/* L = ceil(log2(N - 1)) */
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }

long long dp[1 << 10][1 << 10]; int mask[N];

void init() {
	int b1, b2, d, i;

	for (b2 = 0; b2 < 1 << 10; b2++)
		for (b1 = 0; b1 < 1 << 10; b1++) {
			for (d = 1; d < 9; d++)
				if ((b1 & 1 << d) == b1 && (b2 & 1 << d + 1) == b2) {
					dp[b1][b2] = d;
					break;
				}
			if (dp[b1][b2] != 0)
				continue;
			if ((b1 & 1 << 9) == b1 && (b2 & (1 << 1 | 1 << 0)) == b2) {
				dp[b1][b2] = 9;
				continue;
			}
			dp[b1][b2] = INF;
			for (d = 0; d < 10; d++)
				dp[b1][b2] = min(dp[b1][b2], d < 9 ? dp[b1 & ~(1 << d) | b2 & ~(1 << d + 1)][0] * 10 + d : dp[b1 & ~(1 << 9)][b2 & ~(1 << 0)] * 10 + d);
		}
	for (i = 1; i < N; i++)
		mask[i] = mask[i / 10] | 1 << i % 10;
}

int bb[L + 1][N];

long long solve(int h, int n, int zero) {
	int i, d;
	long long ans;

	if (!zero) {
		int good = 1;

		for (i = 0; i < n; i++)
			if ((mask[i] & bb[h][i]) != bb[h][i]) {
				good = 0;
				break;
			}
		if (good)
			return 0;
	}
	if (n <= 2)
		return dp[bb[h][0]][n == 1 ? 0 : bb[h][1]];
	ans = INF;
	for (d = 0; d < 10; d++) {
		int n_, b;

		n_ = 0, b = 0;
		for (i = 0; i < n; i++) {
			b |= bb[h][i] & ~(1 << (d + i) % 10);
			if (i == n - 1 || (d + i) % 10 == 9) {
				bb[h + 1][n_++] = b;
				b = 0;
			}
		}
		ans = min(ans, solve(h + 1, n_, d == 0) * 10 + d);
	}
	return ans;
}

int main() {
	int n, i;

	init();
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		int d;

		scanf("%d", &d);
		bb[0][i] = 1 << d;
	}
	printf("%lld\n", solve(0, n, 0));
	return 0;
}

Compilation message (stderr)

sequence.c: In function 'init':
sequence.c:19:45: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   19 |     if ((b1 & 1 << d) == b1 && (b2 & 1 << d + 1) == b2) {
      |                                           ~~^~~
sequence.c:31:76: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   31 |     dp[b1][b2] = min(dp[b1][b2], d < 9 ? dp[b1 & ~(1 << d) | b2 & ~(1 << d + 1)][0] * 10 + d : dp[b1 & ~(1 << 9)][b2 & ~(1 << 0)] * 10 + d);
      |                                                                          ~~^~~
sequence.c:31:48: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   31 |     dp[b1][b2] = min(dp[b1][b2], d < 9 ? dp[b1 & ~(1 << d) | b2 & ~(1 << d + 1)][0] * 10 + d : dp[b1 & ~(1 << 9)][b2 & ~(1 << 0)] * 10 + d);
      |                                             ~~~^~~~~~~~~~~
sequence.c: In function 'main':
sequence.c:77:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
sequence.c:81:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   scanf("%d", &d);
      |   ^~~~~~~~~~~~~~~

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