結果

問題 No.2159 Filling 4x4 array
ユーザー vwxyzvwxyz
提出日時 2024-05-03 15:05:14
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 22 ms
46,952 KB
testcase_01 AC 23 ms
46,904 KB
testcase_02 AC 24 ms
46,808 KB
testcase_03 AC 30 ms
47,068 KB
testcase_04 TLE -
testcase_05 AC 33 ms
23,436 KB
testcase_06 AC 239 ms
46,840 KB
testcase_07 AC 24 ms
30,200 KB
testcase_08 AC 161 ms
47,056 KB
testcase_09 AC 29 ms
46,908 KB
testcase_10 AC 39 ms
46,780 KB
testcase_11 AC 65 ms
47,180 KB
testcase_12 AC 33 ms
30,316 KB
testcase_13 AC 143 ms
47,084 KB
testcase_14 AC 456 ms
47,064 KB
testcase_15 AC 211 ms
30,244 KB
testcase_16 AC 38 ms
46,688 KB
testcase_17 AC 40 ms
46,936 KB
testcase_18 AC 38 ms
47,072 KB
testcase_19 AC 88 ms
47,100 KB
testcase_20 AC 24 ms
46,964 KB
testcase_21 AC 414 ms
46,764 KB
testcase_22 AC 25 ms
46,992 KB
testcase_23 AC 158 ms
23,440 KB
testcase_24 AC 60 ms
23,512 KB
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 TLE -
testcase_42 TLE -
testcase_43 TLE -
testcase_44 TLE -
testcase_45 AC 422 ms
23,612 KB
testcase_46 AC 25 ms
23,484 KB
testcase_47 TLE -
testcase_48 AC 26 ms
23,580 KB
testcase_49 TLE -
権限があれば一括ダウンロードができます

ソースコード

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