oj.uz

Submission #494184

# Submission time Handle Problem Language Result Execution time Memory
494184 2021-12-14T16:46:13 Z rainboy L-triominoes (CEOI21_ltriominoes) C
10 / 100
 358 ms 476 KB 
#include <stdio.h>
#include <string.h>

#define N	13
#define M	1000

void advance(char *dp, int n, int c) {
	static char dq[N][1 << N + 1];
	int i, b;

	for (i = 0; i < n; i++)
		memset(dq[i], 0, (1 << n + 1) * sizeof *dq[i]);
	for (b = 0; b < 1 << n; b++)
		if (dp[b]) {
			dq[0][b << 1 | (c & 1)] = 1;
			if ((c & 1) == 0 && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
				dq[0][b << 1 | 1 << n | 1 << n - 1 | 1 << 0] = 1;
		}
	for (i = 0; i + 1 < n; i++)
		for (b = 0; b < 1 << n + 1; b++)
			if (dq[i][b]) {
				int b_ = b << 1 & (1 << n + 1) - 1;

				if ((c & 1 << i + 1) != 0) {
					if ((b & 1 << n) != 0)
						dq[i + 1][b_ | 1 << 0] = 1;
				} else if ((b & 1 << n) != 0) {
					dq[i + 1][b_] = 1;
					if ((b & 1 << 0) == 0 && (b & 1 << n - 1) == 0)
						dq[i + 1][b_ | 1 << 0 | 1 << 1 | 1 << n] = 1;
					if (i + 2 < n && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
						dq[i + 1][b_ | 1 << 0 | 1 << n - 1 | 1 << n] = 1;
				} else {
					if ((b & 1 << 0) == 0)
						dq[i + 1][b_ | 1 << 0 | 1 << 1] = 1;
					if ((b & 1 << n - 1) == 0)
						dq[i + 1][b_ | 1 << 0 | 1 << n] = 1;
				}
			}
	memset(dp, 0, (1 << n) * sizeof *dp);
	for (b = 0; b < 1 << n; b++)
		if (dq[n - 1][b | 1 << n])
			dp[b] = 1;
}

int main() {
	static char dp[1 << N];
	static int bb[M];
	int n, m, k, i, j;

	scanf("%d%d%d", &n, &m, &k);
	while (k--) {
		scanf("%d%d", &i, &j), i--, j--;
		bb[j] |= 1 << i;
	}
	dp[(1 << n) - 1] = 1;
	for (j = 0; j < m; j++)
		advance(dp, n, bb[j]);
	printf(dp[(1 << n) - 1] ? "YES\n" : "NO\n");
	return 0;
}

Compilation message

ltrominoes.c: In function 'advance':
ltrominoes.c:8:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    8 |  static char dq[N][1 << N + 1];
      |                      ^~
ltrominoes.c:12:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   12 |   memset(dq[i], 0, (1 << n + 1) * sizeof *dq[i]);
      |                          ~~^~~
ltrominoes.c:16:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   16 |    if ((c & 1) == 0 && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
      |                                  ~~^~~
ltrominoes.c:16:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   16 |    if ((c & 1) == 0 && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
      |                                                           ~~^~~
ltrominoes.c:17:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   17 |     dq[0][b << 1 | 1 << n | 1 << n - 1 | 1 << 0] = 1;
      |                                  ~~^~~
ltrominoes.c:20:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   20 |   for (b = 0; b < 1 << n + 1; b++)
      |                        ~~^~~
ltrominoes.c:22:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   22 |     int b_ = b << 1 & (1 << n + 1) - 1;
      |                             ~~^~~
ltrominoes.c:22:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   22 |     int b_ = b << 1 & (1 << n + 1) - 1;
      |                       ~~~~~~~~~~~~~^~~
ltrominoes.c:24:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   24 |     if ((c & 1 << i + 1) != 0) {
      |                   ~~^~~
ltrominoes.c:29:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   29 |      if ((b & 1 << 0) == 0 && (b & 1 << n - 1) == 0)
      |                                         ~~^~~
ltrominoes.c:31:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   31 |      if (i + 2 < n && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
      |                                 ~~^~~
ltrominoes.c:31:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   31 |      if (i + 2 < n && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
      |                                                          ~~^~~
ltrominoes.c:32:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   32 |       dq[i + 1][b_ | 1 << 0 | 1 << n - 1 | 1 << n] = 1;
      |                                    ~~^~~
ltrominoes.c:36:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |      if ((b & 1 << n - 1) == 0)
      |                    ~~^~~
ltrominoes.c: In function 'main':
ltrominoes.c:51:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
ltrominoes.c:53:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.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
5 Correct 1 ms 276 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 17 ms 332 KB Output is correct
9 Correct 3 ms 368 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 34 ms 332 KB Output is correct
12 Correct 4 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 341 ms 404 KB Output is correct
17 Correct 41 ms 300 KB Output is correct
18 Correct 170 ms 412 KB Output is correct
19 Correct 5 ms 204 KB Output is correct
20 Correct 353 ms 476 KB Output is correct
21 Correct 163 ms 412 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 4 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 357 ms 476 KB Output is correct
26 Correct 358 ms 460 KB Output is correct
27 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 207 ms 324 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.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
5 Correct 1 ms 276 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 17 ms 332 KB Output is correct
9 Correct 3 ms 368 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 34 ms 332 KB Output is correct
12 Correct 4 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 341 ms 404 KB Output is correct
17 Correct 41 ms 300 KB Output is correct
18 Correct 170 ms 412 KB Output is correct
19 Correct 5 ms 204 KB Output is correct
20 Correct 353 ms 476 KB Output is correct
21 Correct 163 ms 412 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 4 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 357 ms 476 KB Output is correct
26 Correct 358 ms 460 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Runtime error 207 ms 324 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -