結果

問題 No.2159 Filling 4x4 array
ユーザー vwxyzvwxyz
提出日時 2024-05-03 15:07:27
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,379 bytes
コンパイル時間 3,710 ms
コンパイル使用メモリ 276,124 KB
実行使用メモリ 44,056 KB
最終ジャッジ日時 2024-05-03 15:07:40
合計ジャッジ時間 11,522 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
24,012 KB
testcase_01 AC 28 ms
24,044 KB
testcase_02 AC 28 ms
23,936 KB
testcase_03 AC 29 ms
23,936 KB
testcase_04 AC 128 ms
24,344 KB
testcase_05 AC 28 ms
23,936 KB
testcase_06 AC 31 ms
24,104 KB
testcase_07 AC 28 ms
24,108 KB
testcase_08 AC 32 ms
24,020 KB
testcase_09 AC 28 ms
24,064 KB
testcase_10 AC 29 ms
24,064 KB
testcase_11 AC 30 ms
24,020 KB
testcase_12 AC 28 ms
24,064 KB
testcase_13 AC 32 ms
24,064 KB
testcase_14 AC 31 ms
24,020 KB
testcase_15 AC 31 ms
24,128 KB
testcase_16 AC 28 ms
23,936 KB
testcase_17 AC 30 ms
23,936 KB
testcase_18 AC 28 ms
24,064 KB
testcase_19 AC 32 ms
24,064 KB
testcase_20 AC 28 ms
24,132 KB
testcase_21 AC 36 ms
23,956 KB
testcase_22 AC 29 ms
24,064 KB
testcase_23 AC 32 ms
24,064 KB
testcase_24 AC 30 ms
24,064 KB
testcase_25 TLE -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
権限があれば一括ダウンロードができます

ソースコード

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