#pragma GCC optimize("O3,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];
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:1:40: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
1 | #pragma GCC optimize("O3,avx,avx2,sse4")
| ^
ltrominoes.cpp:1:40: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
ltrominoes.cpp:1:40: 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:75: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
33 | static bitset<1 << W> pow(bitset<1 << W> v, bmatrix pow2[31], size_t n)
| ^
ltrominoes.cpp:33:75: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:33:75: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:50:53: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
50 | bitset<1 << W> mul_vec(bitset<1 << W> const &v) const
| ^~~~~
ltrominoes.cpp:50:53: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:50:53: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:63:10: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
63 | int main()
| ^
ltrominoes.cpp:63:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:63:10: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:74:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
74 | for (size_t y = 0; y < 1 << w; ++y)
| ~~^~~~~~~~
ltrominoes.cpp:86:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
86 | if (i == (1 << w) - 1)
| ~~^~~~~~~~~~~~~~~
ltrominoes.cpp:125:51: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
125 | sort(p, p + k, [](auto const &a, auto const &b)
| ^
ltrominoes.cpp:125:51: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:125:51: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
ltrominoes.cpp:149:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
149 | for (size_t i = 0; i < 1 << w; ++i)
| ~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8089 ms |
33160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8058 ms |
33292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8036 ms |
33160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8038 ms |
33172 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8093 ms |
33356 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8089 ms |
33160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
