#include <bits/stdc++.h>
using namespace std;
constexpr size_t W = 13, K = 250, C = 12;
pair<size_t, size_t> p[K];
bitset<1 << W> state[2];
void find_transitions(uint32_t i, uint32_t j, size_t w, bitset<1 << W> &next_state, size_t l = 0)
{
if (i == (1 << w) - 1)
{
next_state[j] = 1;
return;
}
for (size_t h = l; h < w; ++h)
if (!(i & (1 << h)))
{
if (h && !(j & (1 << h)) && !(j & (1 << (h - 1))))
find_transitions(i ^ (1 << h), j ^ (1 << h) ^ (1 << (h - 1)), w, next_state, h + 1);
if (h + 1 < w && !(j & (1 << h)) && !(j & (1 << (h + 1))))
find_transitions(i ^ (1 << h), j ^ (1 << h) ^ (1 << (h + 1)), w, next_state, h + 1);
if (h + 1 < w && !(i & (1 << (h + 1))) && !(j & (1 << h)))
find_transitions(i ^ (1 << h) ^ (1 << (h + 1)), j ^ (1 << h), w, next_state, h + 2);
if (h + 1 < w && !(i & (1 << (h + 1))) && !(j & (1 << (h + 1))))
find_transitions(i ^ (1 << h) ^ (1 << (h + 1)), j ^ (1 << (h + 1)), w, next_state, h + 2);
break;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t w, h, k;
cin >> w >> h >> k;
for (size_t i = 0; i < k; ++i)
cin >> p[i].first >> p[i].second, --p[i].first, --p[i].second;
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 (i < k && !p[i].second)
x |= 1ULL << p[i].first, ++i;
state[0][x] = 1;
}
else
state[0][0] = 1;
auto advance_state = [&](size_t l)
{
if (l <= C)
{
while (l--)
{
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]);
}
}
else
{
bitset<3> curr_components;
for (size_t i = 0; i < 1 << w; ++i)
if (state[0][i])
curr_components[__builtin_popcount(i) % 3] = 1;
state[0].reset();
if (!(w % 3))
{
for (size_t i = 0; i < 1 << w; ++i)
if (curr_components[__builtin_popcount(i) % 3])
state[0][i] = 1;
}
else
{
size_t d = (3 - (l % 3)) % 3;
for (size_t i = 0; i < 1 << w; ++i)
if (curr_components[(__builtin_popcount(i) + d) % 3])
state[0][i] = 1;
}
if (w & 1)
{
size_t j = 0;
for (size_t i = 0; i < w; i += 2)
j |= 1 << i;
state[0][j] = 0;
state[0][~j & ((1 << w) - 1)] = 0;
}
}
};
while (i < k)
{
advance_state(p[i].second - pos);
pos = p[i].second;
size_t x = 0;
size_t j = i;
while (j < k && p[j].second == p[i].second)
x |= 1ULL << 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]);
}
advance_state(h - 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>&, size_t)':
ltrominoes.cpp:11:11: warning: comparison of integer expressions of different signedness: 'uint32_t' {aka 'unsigned int'} and 'int' [-Wsign-compare]
11 | if (i == (1 << w) - 1)
| ~~^~~~~~~~~~~~~~~
ltrominoes.cpp: In lambda function:
ltrominoes.cpp:63:38: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
63 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp:72:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp:78:38: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
78 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp:85:38: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
85 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:112:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
112 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
