Submission #1186888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186888		Unforgettablepl	L-triominoes (CEOI21_ltriominoes)	C++20	0 / 100	8092 ms	8276 KiB

ltrominoes

#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int W,H,K;
    cin >> W >> H >> K;
    vector<pair<int,int>> poss;
    {
        for(int mask1=0;mask1<(1<<W);mask1++){
            for(int mask2=0;mask2<(1<<W);mask2++){
                bool extra = false;
                bool doublesause = false;
                bool works = true;
                for(int i=0;i<W;i++){
                    if(doublesause){
                        doublesause = false;
                        if(!(mask1&(1<<i)) or !(mask2&(1<<i)))works=false;
                    } else if(extra){
                        extra=false;
                        if(!(mask1&(1<<i)) and !(mask2&(1<<i)))works=false;
                        if((mask1&(1<<i)) and (mask2&(1<<i)))doublesause=true;
                    } else {
                        if((mask1&(1<<i)) and (mask2&(1<<i)))extra=true;
                        else if((mask1&(1<<i)) or (mask2&(1<<i)))doublesause=true;
                    }
                }
                if(extra or doublesause)works=false;
                if(works)poss.emplace_back(mask1,mask2);
            }
        }
    }
    vector<pair<int,int>> missing(K);
    for(auto&[a,b]:missing)cin>>b>>a;
    sort(missing.begin(),missing.end());
    auto combine = [&](vector<vector<bool>> &DP1,vector<vector<bool>> &DP2){
        if(DP1.empty())return DP2;
        vector DP((1<<W),vector<bool>(1<<W));
        for(int mask1=0;mask1<(1<<W);mask1++){
            for(int mask2=0;mask2<(1<<W);mask2++){
                for(auto&[mask3,mask4]:poss){
                    if(DP1[mask1][mask3] and DP2[mask4][mask2]){
                        DP[mask1][mask2]=true;
                        break;
                    }
                }
            }
        }
        return DP;
    };
    vector DPbase((1<<W),vector<bool>(1<<W));
    for(int mask=0;mask<(1<<W);mask++)DPbase[mask][mask^((1<<W)-1)]=true;
    function<vector<vector<bool>>(int)> solve = [&](int a){
        if(a==1)return DPbase;
        auto curr = solve(a>>1);
        curr = combine(curr,curr);
        if(a&1)curr=combine(curr,DPbase);
        return curr;
    };
    // auto ans = solve(H);
    // ST
    auto ans = DPbase;
    for(int i=1;i<=H;i++){
        if(ans[0][0]){
            if(H%i == 0)cout << "YES\n";
            else cout << "NO\n";
            break;
        }
        ans = combine(ans,DPbase);
    }

    // ST
    // if(ans[0][0])cout<<"YES\n";
    // else cout << "NO\n";
}

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