Submission #926259

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

ltrominoes

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

struct Matrix {
    vector<vector<ll>> a;
    int n, m;

    Matrix() {

    }

    Matrix(int row, int col) {
        n = row, m = col;
        a = vector<vector<ll>>(row, vector<ll>(col));
    }

    Matrix operator*(const Matrix &mat2) {
        int n2 = mat2.n, m2 = mat2.m;
        Matrix res(n, m2);

        rep(i, n) {
            rep(j, m2) {
                rep(k, m) {
                    ll temp = (a[i][k] * mat2.a[k][j]) % MOD;
                    res.a[i][j] = (res.a[i][j] + temp) % MOD;
                }
            }
        }

        return res;
    }

    void exp(ll b) {
        Matrix res(n, m);
        Matrix curr = *this;
        rep(i, n) res.a[i][i] = 1;

        while (b) {
            if (b & 1) res = res * curr;
            curr = curr * curr;
            b /= 2;
        }

        a = res.a;
    }
};

void solve(int test_case)
{
    ll m,n,k; cin >> m >> n >> k;
    map<ll,ll> mp;

    while(k--){
        ll j,i; cin >> j >> i;
        i--, j--;
        mp[i] |= (1<<j);
    }

    mp[0] = 0;
    mp[n-1] = 0;

    bool dp[1<<m][1<<m];
    memset(dp,0,sizeof dp);

    auto f = [&](ll mask, ll bit){
        if(mask&(1<<bit)) return 1;
        else return 0;
    };

    {
        dp[0][0] = 1;
        queue<pll> q;
        q.push({0,0});
        while(!q.empty()){
            auto [mask2,mask3] = q.front();
            q.pop();

            rep(i,m-1){
                // 2 right, down left
                if(!f(mask2,i) and !f(mask2,i+1) and !f(mask3,i)){
                    ll mask4 = mask2|(1<<i)|(1<<(i+1));
                    ll mask5 = mask3|(1<<i);
                    if(!dp[mask4][mask5]){
                        q.push({mask4,mask5});
                        dp[mask4][mask5] = 1;
                    }
                }

                // 2 right, down right
                if(!f(mask2,i) and !f(mask2,i+1) and !f(mask3,i+1)){
                    ll mask4 = mask2|(1<<i)|(1<<(i+1));
                    ll mask5 = mask3|(1<<(i+1));
                    if(!dp[mask4][mask5]){
                        q.push({mask4,mask5});
                        dp[mask4][mask5] = 1;
                    }
                }

                // 1 up left, 2 down
                if(!f(mask2,i) and !f(mask3,i) and !f(mask3,i+1)){
                    ll mask4 = mask2|(1<<i);
                    ll mask5 = mask3|(1<<i)|(1<<(i+1));
                    if(!dp[mask4][mask5]){
                        q.push({mask4,mask5});
                        dp[mask4][mask5] = 1;
                    }
                }

                // 1 up right, 2 down
                if(!f(mask2,i+1) and !f(mask3,i) and !f(mask3,i+1)){
                    ll mask4 = mask2|(1<<(i+1));
                    ll mask5 = mask3|(1<<i)|(1<<(i+1));
                    if(!dp[mask4][mask5]){
                        q.push({mask4,mask5});
                        dp[mask4][mask5] = 1;
                    }
                }
            }
        }
    }

    Matrix base(1,1<<m);
    ll ptr = 1;
    rep(mask,1<<m){
        if((mp[0]^mask) == ((1<<m)-1)){
            rep(mask2,1<<m){
                base.a[0][mask2] = dp[mask][mask2];
            }
        }
    }

    Matrix mat(1<<m,1<<m);
    rep(i,1<<m){
        ll mask1 = ((1<<m)-1)^i;
        rep(j,1<<m){
            mat.a[i][j] = dp[mask1][j];
        }
    }

    for(auto [i,bad_mask] : mp){
        if(i == 0) conts;
        ll k = i-ptr;

        auto base_copy = base;
        auto mat_copy = mat;
        mat_copy.exp(k);
        base = base*mat_copy;
        Matrix base2(1,1<<m);

        rep(mask,1<<m){
            if(mask&bad_mask){
                base.a[0][mask] = 0;
            }
            else{
                ll more = (1<<m)-1;
                more ^= mask;
                more ^= bad_mask;
                rep(mask2,1<<m){
                    base2.a[0][mask2] = base.a[0][mask]*dp[more][mask2];
                }
            }
        }

        base = base2;
        ptr = i;
    }

    ll ans = base.a[0][0];

    if(ans) yes;
    else no;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message (stderr)

ltrominoes.cpp: In member function 'Matrix Matrix::operator*(const Matrix&)':
ltrominoes.cpp:74:13: warning: unused variable 'n2' [-Wunused-variable]
   74 |         int n2 = mat2.n, m2 = mat2.m;
      |             ^~

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