#pragma GCC optimize("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;
}
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];
bmatrix transitions;
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);
}
}
}
}
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 = 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:1:37: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
1 | #pragma GCC optimize("avx,avx2,sse4")
| ^
ltrominoes.cpp:1:37: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
ltrominoes.cpp:1:37: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
ltrominoes.cpp:12:25: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
12 | bmatrix transpose() const
| ^~~~~
ltrominoes.cpp:12:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:12:25: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:21:41: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
21 | bmatrix operator*(bmatrix const &y) const
| ^~~~~
ltrominoes.cpp:21:41: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:21:41: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:33:27: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
33 | bmatrix pow(size_t n) const
| ^~~~~
ltrominoes.cpp:33:27: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:33:27: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:51:53: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
51 | bitset<1 << W> mul_vec(bitset<1 << W> const &v) const
| ^~~~~
ltrominoes.cpp:51:53: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:51:53: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:64:10: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
64 | int main()
| ^
ltrominoes.cpp:64:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:64:10: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
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:120:51: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
120 | sort(p, p + k, [](auto const &a, auto const &b)
| ^
ltrominoes.cpp:120:51: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:120:51: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:144:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
144 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8064 ms |
33164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8074 ms |
49620 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8048 ms |
33108 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8064 ms |
33084 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8070 ms |
33236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8064 ms |
33164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
