#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll,ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e18;
const ll mod = 1e9 + 7;
vv multiply(vv mat1, vv mat2)
{
ll n1 = mat1.size();
ll m1 = mat1[0].size();
ll n2 = mat2.size();
ll m2 = mat2[0].size();
vv res(n1, v(m2, 0));
for (ll i = 0; i < n1; i++)
{
for (ll j = 0; j < m2; j++)
{
for (ll k = 0; k < n2; k++)
{
res[i][j] += mat1[i][k] * mat2[k][j];
}
}
}
for (ll i =0; i < n1; i++)
{
for (ll j = 0; j < m2; j++)
{
if (res[i][j] > 0) res[i][j] = 1;
}
}
return res;
}
vv matPow(vv mat, ll p)
{
ll n = mat.size();
if (p == 0)
{
vv id(n, v(n, 0));
for (ll i= 0; i < n; i++) id[i][i] = 1;
return id;
}
vv res = matPow(mat, p / 2);
res = multiply(res, res);
if (p % 2 == 1) res = multiply(res, mat);
return res;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll W, H, K;
cin >> W >> H >> K;
ll N = (1 << W);
vp obstructed(K);
for (ll i =0 ; i < K; i++) cin >> obstructed[i].f >> obstructed[i].s;
for (ll i = 0; i < K; i++) {obstructed[i].f--; obstructed[i].s--;}
vv graph(N);
for (ll state = 0; state < N; state++)
{
stack<p> dfs;
dfs.emplace(0, 0);
vvb visited(W + 1, vb(N, false));
while (!dfs.empty())
{
auto top = dfs.top();
dfs.pop();
if (visited[top.f][top.s]) continue;
visited[top.f][top.s] = true;
if (top.f == W) {graph[state].pb(top.s); continue;}
ll i = top.f;
ll next = top.s;
bool current = (state & (1 << i)) == 0;
if (!current) dfs.emplace(i + 1, next);
else
{
bool above = (i < W - 1) && ((state & (1 << (i + 1))) == 0);
bool nextSame = (next & (1 << i)) == 0;
bool nextBelow = (i > 0) && ((next & (1 << (i - 1))) == 0);
bool nextAbove = (i < W - 1) && ((next & (1 << (i + 1))) == 0);
if (above && nextSame) dfs.emplace(i + 2, next ^ (1 << i));
if (above && nextAbove) dfs.emplace(i + 2, next ^ (1 << (i + 1)));
if (nextSame && nextAbove) dfs.emplace(i + 1, next ^ (1 << i) ^ (1 << (i + 1)));
if (nextSame && nextBelow) dfs.emplace(i + 1, next ^ (1 << i) ^ (1 << (i - 1)));
}
}
}
vv matrix(N, v(N, 0));
for (ll i = 0; i < N; i++)
{
for (ll x : graph[i]) matrix[x][i] = 1;
}
vv possible(N, v(1, 0));
ll initial = 0;
sort(all(obstructed),[](p x, p y){return x.s < y.s;});
vector<pair<ll,v>> obstructedRows;
for (ll i = 0; i < K; i++)
{
if (obstructed[i].s == 0)
{
initial ^= (1 << obstructed[i].f);
continue;
}
if (i != 0 && obstructed[i - 1].s == obstructed[i].s) obstructedRows.back().s.pb(obstructed[i].f);
else obstructedRows.eb(obstructed[i].s, v(1, obstructed[i].f));
}
possible[initial][0] = 1;
ll cur = 0;
for (auto x : obstructedRows)
{
ll diff = x.f - cur;
vv mat = matPow(matrix, diff);
vv poss = multiply(mat, possible);
v curObsList;
ll curObsBits = 0;
for (ll y : x.s) {curObsBits ^= (1 << y); curObsList.pb(y);}
for (ll i =0; i < (1 << W); i++)
{
if (i & curObsBits != 0) poss[i][0] = false;
}
for (ll i = 0; i < (1 << W); i++)
{
if (poss[i][0] && (i & curObsBits) == 0)
{
poss[i][0] = false; poss[i ^ curObsBits][0] = true;
}
}
possible = poss;
cur = x.f;
}
ll diff = H - cur - 1;
vv mat = matPow(matrix, diff);
vv poss = multiply(mat, possible);
if (poss.back()[0]) cout << "YES\n";
else cout << "NO\n";
return 0;
}
Compilation message
ltrominoes.cpp: In function 'vv multiply(vv, vv)':
ltrominoes.cpp:33:8: warning: unused variable 'm1' [-Wunused-variable]
33 | ll m1 = mat1[0].size();
| ^~
ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:142:32: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
142 | if (i & curObsBits != 0) poss[i][0] = false;
| ~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Runtime error |
364 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
348 KB |
Output is correct |
| 2 |
Correct |
6 ms |
544 KB |
Output is correct |
| 3 |
Correct |
189 ms |
604 KB |
Output is correct |
| 4 |
Correct |
3 ms |
604 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1372 KB |
Output is correct |
| 6 |
Correct |
3 ms |
604 KB |
Output is correct |
| 7 |
Correct |
2 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
4 ms |
604 KB |
Output is correct |
| 10 |
Correct |
60 ms |
560 KB |
Output is correct |
| 11 |
Correct |
241 ms |
740 KB |
Output is correct |
| 12 |
Correct |
1847 ms |
1468 KB |
Output is correct |
| 13 |
Correct |
50 ms |
344 KB |
Output is correct |
| 14 |
Correct |
46 ms |
536 KB |
Output is correct |
| 15 |
Incorrect |
226 ms |
744 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2599 ms |
4644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
