Submission #487033

#	Time	Username	Problem	Language	Result	Execution time	Memory
487033		rainboy	Trapezi (COI17_trapezi)	C11	100 / 100	17 ms	10068 KiB

trapezi

#include <stdio.h>

#define N	5
#define N_	(N * N * 6)
#define N1	42713087
#define K	4

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

char cc[N * 2][N * 4 + 1];
int ii[N_], jj[N_], ij[N_][K][2], kk[N_], ll[N_ + 1], nn[N_ + 1], n, n_, n1;
char visited[N1];

int good(int i, int j, char c) {
	if (j > 0 && cc[i][j - 1] == c)
		return 0;
	if (j + 1 < n * 4 && cc[i][j + 1] == c)
		return 0;
	if (j % 2 == 0) {
		if (i + 1 < n * 2 && j + 1 < n * 4 && cc[i + 1][j + 1] == c)
			return 0;
	} else {
		if (i > 0 && j > 0 && cc[i - 1][j - 1] == c)
			return 0;
	}
	return 1;
}

void color(int u, int v, int w) {
	int i1 = ii[u], j1 = jj[u], i2 = ii[v], j2 = jj[v], i3 = ii[w], j3 = jj[w];
	char c;

	for (c = '1'; c <= '6'; c++)
		if (good(i1, j1, c) && good(i2, j2, c) && good(i3, j3, c)) {
			cc[i1][j1] = cc[i2][j2] = cc[i3][j3] = c;
			break;
		}
}

int dfs(int i_, int b) {
	int h;

	if (visited[nn[i_] + b])
		return 0;
	if (i_ == n_)
		return 1;
	visited[nn[i_] + b] = 1;
	if ((~b & (1 << ll[i_ + 1] - ll[i_]) - 1) == 0 && dfs(i_ + 1, b >> ll[i_ + 1] - ll[i_]))
		return 1;
	for (h = 0; h < kk[i_]; h++) {
		int j0 = ij[i_][h][0] - ll[i_], j1 = ij[i_][h][1] - ll[i_];

		if ((b & (1 << j0 | 1 << j1)) == 0) {
			int b_ = b | 1 << j0 | 1 << j1 | 1 << i_ - ll[i_];

			if ((~b_ & (1 << ll[i_ + 1] - ll[i_]) - 1) == 0 && dfs(i_ + 1, b_ >> ll[i_ + 1] - ll[i_])) {
				color(i_, ij[i_][h][0], ij[i_][h][1]);
				return 1;
			}
		}
	}
	return 0;
}

int main() {
	static int uu[N * 2][N * 4 + 1];
	int h, i, j, l;

	scanf("%d", &n);
	for (i = 0; i < n + n; i++)
		scanf("%s", cc[i] + (i < n ? 0 : (i - n) * 2 + 1));
	n_ = 0;
	for (i = 0; i < n * 2; i++)
		for (j = 0; j < n * 4; j++)
			if (cc[i][j] == '0') {
				uu[i][j] = n_, ii[n_] = i, jj[n_] = j;
				if (j >= 2 && cc[i][j - 1] == '0' && cc[i][j - 2] == '0')
					ij[n_][kk[n_]][0] = uu[i][j - 2], ij[n_][kk[n_]][1] = uu[i][j - 1], kk[n_]++;
				if (j % 2 == 0) {
					if (i > 0 && j >= 2 && cc[i][j - 1] == '0' && cc[i - 1][j - 2] == '0')
						ij[n_][kk[n_]][0] = uu[i - 1][j - 2], ij[n_][kk[n_]][1] = uu[i][j - 1], kk[n_]++;
				} else {
					if (i > 0 && j >= 2 && cc[i - 1][j - 1] == '0' && cc[i - 1][j - 2] == '0')
						ij[n_][kk[n_]][0] = uu[i - 1][j - 2], ij[n_][kk[n_]][1] = uu[i - 1][j - 1], kk[n_]++;
					if (i > 0 && j > 0 && cc[i - 1][j] == '0' && cc[i - 1][j - 1] == '0')
						ij[n_][kk[n_]][0] = uu[i - 1][j - 1], ij[n_][kk[n_]][1] = uu[i - 1][j], kk[n_]++;
					if (i > 0 && j > 0 && cc[i - 1][j - 1] == '0' && cc[i][j - 1] == '0')
						ij[n_][kk[n_]][0] = uu[i - 1][j - 1], ij[n_][kk[n_]][1] = uu[i][j - 1], kk[n_]++;
				}
				n_++;
			}
	ll[n_] = l = n_;
	for (i = n_ - 1; i >= 0; i--) {
		for (h = 0; h < kk[i]; h++)
			l = min(l, ij[i][h][0]);
		if (l > i) {
			printf("nemoguce\n");
			return 0;
		}
		ll[i] = l;
	}
	for (i = 0; i < n_; i++)
		nn[i + 1] = n1 += 1 << i - ll[i];
	if (dfs(0, 0))
		for (i = 0; i < n + n; i++)
			printf("%s\n", cc[i] + (i < n ? 0 : (i - n) * 2 + 1));
	else
		printf("nemoguce\n");
	return 0;
}

Compilation message (stderr)

trapezi.c: In function 'dfs':
trapezi.c:48:29: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   48 |  if ((~b & (1 << ll[i_ + 1] - ll[i_]) - 1) == 0 && dfs(i_ + 1, b >> ll[i_ + 1] - ll[i_]))
      |                  ~~~~~~~~~~~^~~~~~~~
trapezi.c:48:39: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   48 |  if ((~b & (1 << ll[i_ + 1] - ll[i_]) - 1) == 0 && dfs(i_ + 1, b >> ll[i_ + 1] - ll[i_]))
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
trapezi.c:48:80: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   48 |  if ((~b & (1 << ll[i_ + 1] - ll[i_]) - 1) == 0 && dfs(i_ + 1, b >> ll[i_ + 1] - ll[i_]))
      |                                                                     ~~~~~~~~~~~^~~~~~~~
trapezi.c:54:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   54 |    int b_ = b | 1 << j0 | 1 << j1 | 1 << i_ - ll[i_];
      |                                          ~~~^~~~~~~~
trapezi.c:56:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |    if ((~b_ & (1 << ll[i_ + 1] - ll[i_]) - 1) == 0 && dfs(i_ + 1, b_ >> ll[i_ + 1] - ll[i_])) {
      |                     ~~~~~~~~~~~^~~~~~~~
trapezi.c:56:42: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   56 |    if ((~b_ & (1 << ll[i_ + 1] - ll[i_]) - 1) == 0 && dfs(i_ + 1, b_ >> ll[i_ + 1] - ll[i_])) {
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
trapezi.c:56:84: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   56 |    if ((~b_ & (1 << ll[i_ + 1] - ll[i_]) - 1) == 0 && dfs(i_ + 1, b_ >> ll[i_ + 1] - ll[i_])) {
      |                                                                         ~~~~~~~~~~~^~~~~~~~
trapezi.c: In function 'main':
trapezi.c:103:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  103 |   nn[i + 1] = n1 += 1 << i - ll[i];
      |                          ~~^~~~~~~
trapezi.c:69:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
trapezi.c:71:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%s", cc[i] + (i < n ? 0 : (i - n) * 2 + 1));
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 22 / 22
• Subtask 5: 37 / 37