#include <stdio.h>
#include <string.h>
#define N 13
#define M 1000
#define R 20
#define K 250
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
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 ii[K], jj[K];
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (jj[hh[j]] == jj[h])
j++;
else if (jj[hh[j]] < jj[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
void advance0(char *dp, int n, int k) {
if (k >= R)
k -= ((K - R) / 6 + 1) * 6;
while (k--)
advance(dp, n, 0);
}
int main() {
#if 0
static char dp_[R][1 << N];
int n, b;
for (n = 1; n <= 13; n++) {
printf("trying %d\n", n);
for (b = 0; b < 1 << n; b++) {
int b_, h;
memset(dp_[0], 0, (1 << n) * sizeof *dp_[0]), dp_[0][b] = 1;
for (h = 1; h < R; h++) {
memcpy(dp_[h], dp_[h - 1], (1 << n) * sizeof *dp_[h - 1]);
advance(dp_[h], n, 0);
}
for (b_ = 0; b_ < 1 << n; b_++)
if (dp_[R - 1][b_] != dp_[R - 7][b_]) {
printf("conjecture disproven :(\n");
return 0;
}
}
}
#else
static char dp[1 << N];
static int hh[K];
int n, m, k, h, h_, j, j_, b;
scanf("%d%d%d", &n, &m, &k);
for (h = 0; h < k; h++) {
scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
hh[h] = h;
}
sort(hh, 0, k);
dp[(1 << n) - 1] = 1;
for (h = 0, j = -1; h < k; h = h_) {
j_ = jj[hh[h]];
h_ = h;
b = 0;
while (h_ < k && jj[hh[h_]] == j_)
b |= 1 << ii[hh[h_++]];
advance0(dp, n, j_ - 1 - j), advance(dp, n, b);
j = j_;
}
advance0(dp, n, m - 1 - j);
printf(dp[(1 << n) - 1] ? "YES\n" : "NO\n");
#endif
return 0;
}
Compilation message
ltrominoes.c: In function 'advance':
ltrominoes.c:16:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
16 | static char dq[N][1 << N + 1];
| ^~
ltrominoes.c:20:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
20 | memset(dq[i], 0, (1 << n + 1) * sizeof *dq[i]);
| ~~^~~
ltrominoes.c:24:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
24 | if ((c & 1) == 0 && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
| ~~^~~
ltrominoes.c:24:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
24 | if ((c & 1) == 0 && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
| ~~^~~
ltrominoes.c:25:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
25 | dq[0][b << 1 | 1 << n | 1 << n - 1 | 1 << 0] = 1;
| ~~^~~
ltrominoes.c:28:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
28 | for (b = 0; b < 1 << n + 1; b++)
| ~~^~~
ltrominoes.c:30:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
30 | int b_ = b << 1 & (1 << n + 1) - 1;
| ~~^~~
ltrominoes.c:30:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
30 | int b_ = b << 1 & (1 << n + 1) - 1;
| ~~~~~~~~~~~~~^~~
ltrominoes.c:32:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
32 | if ((c & 1 << i + 1) != 0) {
| ~~^~~
ltrominoes.c:37:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
37 | if ((b & 1 << 0) == 0 && (b & 1 << n - 1) == 0)
| ~~^~~
ltrominoes.c:39:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
39 | if (i + 2 < n && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
| ~~^~~
ltrominoes.c:39:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
39 | if (i + 2 < n && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
| ~~^~~
ltrominoes.c:40:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
40 | dq[i + 1][b_ | 1 << 0 | 1 << n - 1 | 1 << n] = 1;
| ~~^~~
ltrominoes.c:44:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
44 | if ((b & 1 << n - 1) == 0)
| ~~^~~
ltrominoes.c: In function 'main':
ltrominoes.c:109:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | scanf("%d%d%d", &n, &m, &k);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
ltrominoes.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8064 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8096 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8099 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8076 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8087 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8064 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
