Submission #1214804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214804		biank	L-triominoes (CEOI21_ltriominoes)	C++20	45 / 100	389 ms	776 KiB

ltrominoes

#include <bits/stdc++.h>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;

bool can(int h, int w){
    if(h%3!=0) return false;
    if(w==1) return false;
    if(w%2==0) return true;
    if(h%2==0) return true;
    if(w>=5&&h>=9) return true;
    return false;
}

bool solve(const vector<vi> &v){
    int h=sz(v),w=sz(v[0]);
    vi dp(1<<(w+1),0);
    dp[(1<<(w+1))-1]=1;
    forn(i,h) forn(j,w){
        vi nextDP(1<<(w+1),0);
        auto upd=[&](int mask, int a, int b){
            if((mask>>a&1)==0&&(mask>>b&1)==0){
                int nextMask=mask^(1<<a)^(1<<b);
                if((nextMask&1)==0) return;
                nextMask>>=1,nextMask|=1<<w;
                nextDP[nextMask]=1;
            }
        };
        if(v[i][j]==0){
            forn(mask,1<<(w+1)) if(dp[mask]){
                if(i>=1&&j>=1){
                    upd(mask,1,w);
                    upd(mask,0,w);
                    upd(mask,0,1);
                }
                if(i>=1&&j+1<w){
                    upd(mask,1,2);
                }
                if((mask&1)==1) nextDP[mask>>1]=1;
            }
        }else{
            forn(mask,1<<(w+1)) if((mask&1)==1&&dp[mask]){
                int nextMask=mask>>1;
                nextMask|=1<<w;
                nextDP[nextMask]=1;
            }
        }
        swap(dp,nextDP);
    }
    return dp[(1<<(w+1))-1];
}

const int K=64;
const int B=31;

using mat=array<array<bool,K>,K>;

mat operator*(const mat &a, const mat &b){
    mat c;
    forn(i,K) forn(j,K) c[i][j]=0;
    forn(i,K) forn(k,K) forn(j,K){
        c[i][j]|=a[i][k]&b[k][j];
    }
    return c;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int w,h,k;
    cin>>w>>h>>k;
    if(k==0){
        if(can(w,h)||can(h,w)) cout<<"YES\n";
        else cout<<"NO\n";
        return 0;
    }
    if(h<=1000){
        vector<vi> v(h,vi(w,0));
        forn(i,k){
            int x,y;
            cin>>x>>y;
            --x,--y;
            v[y][x]=1;
        }
        if(solve(v)){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
        return 0;
    }
    mat can[B];
    forn(i,K) forn(j,K) can[0][i][j]=0;
    forn(mask1,1<<w) forn(mask2,1<<w){
        vector<vi> v(2,vi(w,0));
        forn(i,w) if(mask1>>i&1) v[0][i]=1;
        forn(i,w) if(mask2>>i&1^1) v[1][i]=1;
        can[0][mask1][mask2]=solve(v);
    }
    forn(i,B-1){
        can[i+1]=can[i]*can[i];
    }
    vi x(k),y(k);
    forn(i,k){
        cin>>x[i]>>y[i];
        x[i]--,y[i]--;
    }
    vi vals=y;
    vals.pb(0);
    vals.pb(h-1);
    sort(all(vals));
    vals.erase(unique(all(vals)),end(vals));
    vi blocked(sz(vals),0);
    forn(i,k){
        int pos=int(lower_bound(all(vals),y[i])-begin(vals));
        blocked[pos]|=1<<x[i];
    }
    vi dp(1<<w,0);
    dp[0]=1;
    forsn(i,1,sz(vals)){
        int diff=vals[i]-vals[i-1];
        mat m;
        forn(i,K) forn(j,K) m[i][j]=i==j;
        forn(i,B) if(diff>>i&1) m=m*can[i];
        vi nextDP(1<<w,0);
        forn(mask1,1<<w) if(dp[mask1]){
            forn(mask2,1<<w) if((blocked[i]&mask2)==0&&m[mask1|blocked[i-1]][mask2]){
                nextDP[mask2]=1;
            }
        }
        swap(dp,nextDP);
    }
    int need=((1<<w)-1)^blocked.back();
    if(dp[need]) cout<<"YES\n";
    else cout<<"NO\n";
    
    return 0;
}

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