#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse4")
#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;
}
static bitset<1 << W> pow(bitset<1 << W> v, bmatrix pow2[31], size_t n)
{
size_t i = 1;
while (n)
{
if (n & 1)
{
v = pow2[i].mul_vec(v);
}
n >>= 1;
++i;
}
return v;
}
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];
bmatrix transitions, pow2[31];
bitset<1 << W> state, state2;
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 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.mat[j][y] = 1;
continue;
}
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));
q.push((ni << W) | nj);
}
if (h + 1 < w && !(j & (1 << h)) && !(j & (1 << (h + 1))))
{
size_t ni = i ^ (1 << h), nj = j ^ (1 << h) ^ (1 << (h + 1));
q.push((ni << W) | nj);
}
if (h + 1 < w && !(i & (1 << (h + 1))) && !(j & (1 << h)))
{
size_t ni = i ^ (1 << h) ^ (1 << (h + 1)), nj = j ^ (1 << h);
q.push((ni << W) | nj);
}
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));
q.push((ni << W) | nj);
}
}
}
}
pow2[1] = transitions;
for (size_t i = 2; i < 31; ++i)
{
pow2[i] = pow2[i - 1] * pow2[i - 1];
bool all_one = 1;
for (size_t j = 0; j < 1 << w; ++j)
all_one &= pow2[i].mat[j].count() == 1 << w;
if (all_one)
{
for (size_t j = i + 1; j < 31; ++j)
pow2[j] = pow2[i];
break;
}
}
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 |= 1 << p[i].first, ++i;
state[x] = 1;
}
else
state[0] = 1;
while (i < k)
{
state = bmatrix::pow(state, pow2, 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 |= 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 = bmatrix::pow(state, pow2, h - 1 - pos);
}
cout << (state[(1 << w) - 1] ? "YES" : "NO") << '\n';
}
Compilation message
ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:75:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
75 | for (size_t y = 0; y < 1 << w; ++y)
| ~~^~~~~~~~
ltrominoes.cpp:87:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
87 | if (i == (1 << w) - 1)
| ~~^~~~~~~~~~~~~~~
ltrominoes.cpp:125:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
125 | for (size_t j = 0; j < 1 << w; ++j)
| ~~^~~~~~~~
ltrominoes.cpp:126:47: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
126 | all_one &= pow2[i].mat[j].count() == 1 << w;
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
ltrominoes.cpp:160:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
160 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8082 ms |
33160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8074 ms |
33292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8041 ms |
33160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8070 ms |
33172 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8074 ms |
33308 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8082 ms |
33160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
