結果

問題 No.2159 Filling 4x4 array
ユーザー vwxyz
提出日時 2024-05-03 15:07:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,379 bytes
コンパイル時間 3,656 ms
コンパイル使用メモリ 277,792 KB
実行使用メモリ 61,872 KB
最終ジャッジ日時 2024-11-24 16:18:56
合計ジャッジ時間 126,673 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 25 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int mod = 998244353;
vector<int> pow5 = {1, 5, 25, 125, 625, 3125, 15625, 78125};

vector<map<vector<int>, int>> cnt(390625);
map<pair<vector<int>,vector<int>>, int> memo;


int solve(vector<int>& H, vector<int>& W) {
    if (memo.find({H,W}) != memo.end()) {
        return memo[{H,W}];
    }
    for (int h : H) {
        if (h < 0)
            return 0;
    }
    for (int w : W) {
        if (w < 0)
            return 0;
    }
    if (all_of(H.begin(), H.end(), [](int h){ return h == 0; }) && all_of(W.begin(), W.end(), [](int w){ return w == 0; }))
        return 1;
    int retu = 0;
    int s=0;
    for(int i=0;i<4;i++){
        s+=H[i]%2*pow5[i]+W[i]%2*pow5[i+4];
    }
    for (auto &[key, c] : cnt[s]) {
        bool valid=true;
        for (size_t i = 0; i < 4; ++i) {
            if (H[i] < key[i] || H[i] % 2 != key[i] % 2) {
                valid = false;
                break;
            }
            if (W[i] < key[i+4] || W[i] % 2 != key[i+4] % 2) {
                valid = false;
                break;
            }
        }
        if (valid) {
            vector<int> new_H(4), new_W(4);
            for(int i=0;i<4;i++){
                new_H[i]=(H[i]-key[i])>>1;
                new_W[i]=(W[i]-key[i+4])>>1;
            }
            sort(new_H.begin(),new_H.end());
            sort(new_W.begin(),new_W.end());
            retu += solve(new_H, new_W) * c;
            retu %= mod;
        }
    }
    memo[{H,W}]=retu;
    return retu;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    vector<int> HW(8);
    for (int i = 0; i < 8; ++i) {
        cin >> HW[i];
        HW[i] -= 4;
    }
    vector<int> H(HW.begin(), HW.begin() + 4);
    vector<int> W(HW.begin() + 4, HW.end());
    sort(H.begin(), H.end());
    sort(W.begin(), W.end());
    
    for (int bit = 0; bit < (1 << 16); ++bit) {
        vector<int> HHWW(8);
        for (int h = 0; h < 4; ++h) {
            for (int w = 0; w < 4; ++w) {
                HHWW[h] += (bit >> (h * 4 + w)) & 1;
                HHWW[4+w] += (bit >> (h * 4 + w)) & 1;
            }
        }
        int s=0;
        for(int i=0;i<8;i++){
            s+=HHWW[i]%2*pow5[i];
        }
        cnt[s][HHWW] += 1;
    }
    
    int ans = solve(H, W);
    cout << ans << endl;
    
    return 0;
}
0