oj.uz

Submission #487033

# Submission time Handle Problem Language Result Execution time Memory
487033 2021-11-13T21:51:13 Z rainboy Trapezi (COI17_trapezi) C
100 / 100
 17 ms 10068 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 9 ms 9932 KB Output is correct
6 Correct 17 ms 10068 KB Output is correct
7 Correct 2 ms 2380 KB Output is correct
8 Correct 2 ms 2380 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 5 ms 2764 KB Output is correct