Submission #955504

#	Time	Username	Problem	Language	Result	Execution time	Memory
955504		yoav_s	L-triominoes (CEOI21_ltriominoes)	C++17	0 / 100	2599 ms	524288 KiB

ltrominoes

#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 (stderr)

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;
      |                     ~~~~~~~~~~~^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20