結果

問題 No.2159 Filling 4x4 array
コンテスト
ユーザー vwxyz
提出日時 2024-05-03 15:05:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,333 bytes
コンパイル時間 3,257 ms
コンパイル使用メモリ 275,916 KB
実行使用メモリ 47,180 KB
最終ジャッジ日時 2024-11-24 16:14:43
合計ジャッジ時間 145,604 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 TLE * 1
other AC * 23 TLE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

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;
        }
    }
    return retu;
}

int 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