#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
constexpr size_t W = 13, K = 250;
pair<size_t, size_t> p[K];
vector<uint32_t> transitions[1 << 13];
bitset<1 << W> state[2];
void find_transitions(uint32_t i, uint32_t j, size_t w, bitset<1 << W> &next_state)
{
if (i == (1 << w) - 1)
{
next_state[j] = 1;
return;
}
for (size_t h = 0; h < w; ++h)
if (!(i & (1 << h)))
{
if (h && !(j & (1 << h)) && !(j & (1 << (h - 1))))
{
size_t ni = i ^ (1 << h), nj = j ^ (1 << h) ^ (1 << (h - 1));
find_transitions(ni, nj, w, next_state);
}
if (h + 1 < w && !(j & (1 << h)) && !(j & (1 << (h + 1))))
{
size_t ni = i ^ (1 << h), nj = j ^ (1 << h) ^ (1 << (h + 1));
find_transitions(ni, nj, w, next_state);
}
if (h + 1 < w && !(i & (1 << (h + 1))) && !(j & (1 << h)))
{
size_t ni = i ^ (1 << h) ^ (1 << (h + 1)), nj = j ^ (1 << h);
find_transitions(ni, nj, w, next_state);
}
if (h + 1 < w && !(i & (1 << (h + 1))) && !(j & (1 << (h + 1))))
{
size_t ni = i ^ (1 << h) ^ (1 << (h + 1)), nj = j ^ (1 << (h + 1));
find_transitions(ni, nj, w, next_state);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t w, h, k;
cin >> w >> h >> k;
assert(h <= 1000);
for (size_t i = 0; i < k; ++i)
cin >> p[i].first >> p[i].second, --p[i].first, --p[i].second;
for (size_t y = 0; y < 1 << w; ++y)
{
queue<uint32_t> q;
q.push(y << W);
while (!q.empty())
{
uint32_t u = q.front();
q.pop();
size_t i = u >> W, j = u & ((1 << W) - 1);
if (i == (1 << w) - 1)
{
transitions[y].push_back(j);
continue;
}
}
}
if (w >= 12)
exit(-1);
sort(p, p + k, [](auto const &a, auto const &b)
{ return a.second < b.second; });
size_t i = 0, pos = 0;
if (k && !p[0].second)
{
size_t x = 0;
while (!p[i].second)
x |= 1ULL << p[i].first, ++i;
state[0][x] = 1;
}
else
state[0][0] = 1;
while (i < k)
{
while (pos < p[i].second)
{
state[1].reset();
for (size_t i = 0; i < 1 << w; ++i)
if (state[0][i])
find_transitions(i, 0, w, state[1]);
swap(state[0], state[1]);
++pos;
}
size_t x = 0;
size_t j = i;
while (j < k && p[j].second == p[i].second)
x |= 1 << p[j].first, ++j;
i = j;
state[1].reset();
for (size_t i = 0; i < 1 << w; ++i)
if (!(i & x) && state[0][i])
state[1][i ^ x] = 1;
swap(state[0], state[1]);
}
while (pos < h - 1)
{
state[1].reset();
for (size_t i = 0; i < 1 << w; ++i)
if (state[0][i])
find_transitions(i, 0, w, state[1]);
swap(state[0], state[1]);
++pos;
}
cout << (state[0][(1 << w) - 1] ? "YES" : "NO") << '\n';
}
Compilation message
ltrominoes.cpp: In function 'void find_transitions(uint32_t, uint32_t, size_t, std::bitset<8192>&)':
ltrominoes.cpp:14:11: warning: comparison of integer expressions of different signedness: 'uint32_t' {aka 'unsigned int'} and 'int' [-Wsign-compare]
14 | if (i == (1 << w) - 1)
| ~~^~~~~~~~~~~~~~~
ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:58:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
58 | for (size_t y = 0; y < 1 << w; ++y)
| ~~^~~~~~~~
ltrominoes.cpp:70:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | if (i == (1 << w) - 1)
| ~~^~~~~~~~~~~~~~~
ltrominoes.cpp:99:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
99 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp:113:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
113 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp:122:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
122 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
524 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
520 KB |
Output is correct |
| 7 |
Correct |
5 ms |
468 KB |
Output is correct |
| 8 |
Runtime error |
1 ms |
468 KB |
Execution failed because the return code was nonzero |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
852 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
852 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
852 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
852 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
524 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
520 KB |
Output is correct |
| 7 |
Correct |
5 ms |
468 KB |
Output is correct |
| 8 |
Runtime error |
1 ms |
468 KB |
Execution failed because the return code was nonzero |
| 9 |
Halted |
0 ms |
0 KB |
- |
