#include <bits/stdc++.h>
using namespace std;
constexpr size_t W = 13, K = 250, C = 12;
size_t w;
pair<size_t, size_t> p[K];
bitset<1 << W> state[2];
size_t r, s;
void find_transitions(uint32_t i, uint32_t j, 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)), 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)), 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), 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)), next_state, h + 2);
break;
}
}
void 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, state[1]);
swap(state[0], state[1]);
}
}
else
{
bitset<3> curr_components;
for (size_t i = 0; i < 1 << w; ++i)
if (i != s && state[0][i] && !curr_components[__builtin_popcount(i) % 3])
{
curr_components[__builtin_popcount(i) % 3] = 1;
}
state[0].reset();
if (!(w % 3))
{
for (size_t i = 0; i < 1 << w; ++i)
if (i != r && curr_components[__builtin_popcount(i) % 3])
state[0][i] = 1;
}
else
{
size_t d = (3 - ((l * w) % 3)) % 3;
for (size_t i = 0; i < 1 << w; ++i)
if (i != r && curr_components[(__builtin_popcount(i) + d) % 3])
state[0][i] = 1;
}
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t h, k;
cin >> w >> h >> k;
for (size_t i = 0; i < w; i += 2)
r |= 1 << i;
for (size_t i = 1; i < w; i += 2)
s |= 1 << i;
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;
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, std::bitset<8192>&, size_t)':
ltrominoes.cpp:13:11: warning: comparison of integer expressions of different signedness: 'uint32_t' {aka 'unsigned int'} and 'int' [-Wsign-compare]
13 | if (i == (1 << w) - 1)
| ~~^~~~~~~~~~~~~~~
ltrominoes.cpp: In function 'void advance_state(size_t)':
ltrominoes.cpp:41:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp:50:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp:58:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
58 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp:65:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
65 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp: In function 'int main()':
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)
| ~~^~~~~~~~
| # |
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 |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 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 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
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 |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 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 |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
