Submission #1183662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183662		Mighilon	L-triominoes (CEOI21_ltriominoes)	C++20	100 / 100	2354 ms	1744 KiB

ltrominoes

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const ll MOD = 998244353;
const int mxN = 3e5+5;

void solve(){
    // int w,h;
    // cin>>w>>h;
    // vector<vector<vl>> dp(h+2,vector<vl>(w+2,vl(1<<(w+1))));
    // dp[0][1][0]=1;
    // #define _s(i) ((s>>(i))&1)
    // F0R(i,h){
    //     FOR(j,1,w+1){
    //         F0R(s,1<<(w+1)){
    //             if(!dp[i][j][s])continue;
    //             if(_s(j)){
    //                 dp[i][j+1][s^(1<<j)]+=dp[i][j][s];
    //             }
    //             // #     ##   ##    #
    //             // ##     #   #    ##
    //             if(j<w&&!_s(j)&&!_s(j-1)&&!_s(j+1)){
    //                 dp[i][j+1][s^(1<<(j-1))^(1<<(j+1))]+=dp[i][j][s];
    //             }
    //             if(j>=2&&!_s(j)&&!_s(j-1)&&!_s(j-2)){
    //                 dp[i][j+1][s^(1<<(j-1))^(1<<(j-2))]+=dp[i][j][s];
    //             }
    //             if(j<w&&!_s(j)&&!_s(j-1)){
    //                 dp[i][j+1][s^(1<<j)^(1<<(j-1))]+=dp[i][j][s];
    //             }
    //             if(j<w&&!_s(j)&&!_s(j+1)){
    //                 dp[i][j+1][s^(1<<j)^(1<<(j+1))]+=dp[i][j][s];
    //             }
    //         }
    //     }
    //     F0R(s,1<<(w)){
    //         dp[i+1][1][s<<1]=dp[i][w+1][s];
    //     }
    // }
    // cout<<dp[h][1][0]<<nl;
    int w,H,k,h=0;
    cin>>w>>H>>k; 
    vpi p(k);

    F0R(i,k){
        cin>>p[i].f>>p[i].s;
        p[i].f;p[i].s;
    }
    sort(all(p));
    p.erase(unique(all(p)),p.end());
    k=sz(p);
    dbg(p)
    // if((1LL*w*h-k)%3!=0){
    //     cout<<"NO"<<nl;
    //     return;
    // }
    sort(all(p),[](pi& a,pi & b){return a.s<b.s;});
    vi he(k);
    F0R(i,k){
        if(i) he[i]=he[i-1]+min(p[i].s-p[i-1].s,(p[i].s-p[i-1].s-1)%6+13);
        else he[i]=min(p[i].s,(p[i].s-1)%6+13);
        h=he[i];
    }
    if(k) h=he[k-1]+min(H-p[k-1].s,(H-p[k-1].s-1)%6+13);
    else h=min(H,(H-1)%6+13);
    dbg(h)
    dbg(he)
    vector<vi> dp(w+2,vi(1<<(w+1)));
    vector<vi> a(h+1,vi(w));
    int s_=0;
    F0R(i,k){
        p[i].f--;
        p[i].s--;
        he[i]--;
        a[he[i]][p[i].f]=1;
        if(!p[i].s)
            s_|=(1<<p[i].f);
    }

    dbg(a)
    dbg(s_)
    dp[1][s_<<1]=1;
    #define _s(i) ((s>>(i))&1)
    F0R(i,h){
        dbg(i,dp)
        F0R(s,1<<(w+1)){
            if(!dp[1][s])continue;
            string tmp="";
            F0R(k,w+1){
                if(_s(k))tmp.pb('#');
                else tmp.pb('.');
            }
            dbg(i,s,tmp);
        }

        FOR(j,1,w+1){
            F0R(s,1<<(w+1)){
                if(!dp[j][s])continue;
                if(_s(j)){
                    dbg(1)
                    dp[j+1][s^(1<<j)]|=dp[j][s];
                }
                if(a[i][j-1]&&!_s(j)){
                    dbg(2)
                    dbg(s)
                    dp[j+1][s]|=dp[j][s];
                }
                // #  ## ##  #
                // ##  # #  ##
                if(j<w&&!_s(j)&&!_s(j-1)&&!_s(j+1)&&!a[i][j-1]&&!a[i][j]&&!a[i+1][j-1]){
                    dbg(3)
                    int t=s^(1<<(j-1))^(1<<(j+1));
                    dp[j+1][t]|=dp[j][s];
                }
                if(j>=2&&!_s(j)&&!_s(j-1)&&!_s(j-2)&&!a[i][j-1]&&!a[i+1][j-1]&&!a[i+1][j-2]){
                    dbg(4);
                    int t=s^(1<<(j-2))^(1<<(j-1));
                    dp[j+1][t]|=dp[j][s];
                }
                if(j<w&&!_s(j)&&!_s(j-1)&&!a[i][j-1]&&!a[i+1][j-1]&&!a[i+1][j]){
                    dbg(5)
                    int t=s^(1<<(j))^(1<<(j-1));
                    dp[j+1][t]|=dp[j][s];
                }
                if(j<w&&!_s(j)&&!_s(j+1)&&!a[i][j-1]&&!a[i][j]&&!a[i+1][j]){
                    dbg(6)
                    int t=s^(1<<(j))^(1<<(j+1));
                    dp[j+1][t]|=dp[j][s];
                }
            }
        }
        dbg(i,dp)
        F0R(s,1<<(w+1)){
            dp[1][s]=0;
        }
        F0R(s,1<<(w)){
            dp[1][s<<1]=dp[w+1][s];
        }
        FOR(j,2,w+2){
            F0R(s,1<<(w+1)){
                dp[j][s]=0;
            }
        }
    }
    dbg(dp)
    if(dp[1][0])
        cout<<"YES"<<nl;
    else cout<<"NO"<<nl;
}
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

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