#include <bits/stdc++.h>
using namespace std;
constexpr size_t W = 13, K = 250;
struct bmatrix
{
bitset<1 << W> mat[1 << W];
bmatrix transpose() const
{
bmatrix res;
for (size_t i = 0; i < 1U << W; ++i)
for (size_t j = 0; j < 1U << W; ++j)
res.mat[i][j] = mat[j][i];
return res;
}
bmatrix operator*(bmatrix const &y) const
{
bmatrix x = y.transpose();
bmatrix res;
for (size_t i = 0; i < 1U << W; ++i)
for (size_t j = 0; j < 1U << W; ++j)
res.mat[i][j] = (mat[i] & x.mat[j]).any();
return res;
}
bmatrix pow(size_t n) const
{
bmatrix a = *this;
bmatrix res;
for (size_t i = 0; i < 1U << W; ++i)
res.mat[i][i] = 1;
while (n)
{
if (n & 1)
res = res * a;
a = a * a;
n >>= 1;
}
return res;
}
bitset<1 << W> mul_vec(bitset<1 << W> const &v) const
{
bitset<1 << W> res;
for (size_t i = 0; i < 1U << W; ++i)
res[i] = (mat[i] & v).any();
return res;
}
};
pair<size_t, size_t> p[K];
bitset<1 << W> f[1 << W];
vector<uint32_t> pre[1 << W][1 << W];
bitset<1 << (W << 1)> visited;
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;
for (size_t i = 0; i < 1U << w; ++i)
f[i][0] = 1;
for (size_t i = 0; i < 1U << w; ++i)
for (size_t j = 0; j < 1U << w; ++j)
if (f[i][j])
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));
f[ni][nj] = 1;
pre[ni][nj].push_back((i << W) | j);
}
if (h + 1 < w && !(j & (1 << h)) && !(j & (1 << (h + 1))))
{
size_t ni = i ^ (1 << h), nj = j ^ (1 << h) ^ (1 << (h + 1));
f[ni][j] = 1;
pre[ni][nj].push_back((i << W) | j);
}
if (h + 1 < w && !(i & (1 << (h + 1))) && !(j & (1 << h)))
{
size_t ni = i ^ (1 << h) ^ (1 << (h + 1)), nj = j ^ (1 << h);
f[ni][nj] = 1;
pre[ni][nj].push_back((i << W) | j);
}
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));
f[ni][nj] = 1;
pre[ni][nj].push_back((i << W) | j);
}
}
bmatrix transitions;
for (size_t i = 0; i < 1 << w; ++i)
{
queue<uint32_t> q;
q.push((((1 << w) - 1) << W) | i);
visited.reset();
while (!q.empty())
{
uint32_t u = q.front();
q.pop();
if (!(u & ((1 << W) - 1)))
{
transitions.mat[i][u >> W] = 1;
}
for (auto const &v : pre[u >> W][u & ((1 << W) - 1)])
if (!visited[v])
{
q.push(v);
visited[v] = 1;
}
}
}
sort(p, p + k, [](auto const &a, auto const &b)
{ return a.second < b.second; });
bitset<1 << W> state, state2;
size_t i = 0, pos = 0;
if (k && !p[0].second)
{
size_t x = 0;
while (!p[i].second)
x |= 1 << p[i].first, ++i;
state[x] = 1;
}
else
state[0] = 1;
while (i < k)
{
state = transitions.pow(p[i].second - pos).mul_vec(state);
pos = p[i].second;
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;
state2.reset();
for (size_t i = 0; i < 1 << w; ++i)
if (!(i & x) && state[i])
state2[i ^ x] = 1;
state = state2;
}
if (pos != h - 1)
{
state = transitions.pow(h - 1 - pos).mul_vec(state);
}
cout << (state[(1 << w) - 1] ? "YES" : "NO") << '\n';
}
Compilation message
ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:109:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
109 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
ltrominoes.cpp:159:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
159 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
190 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
169 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
173 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
161 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
162 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
190 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
