結果

問題 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,656 ms
コンパイル使用メモリ 277,792 KB
実行使用メモリ 61,872 KB
最終ジャッジ日時 2024-11-24 16:18:56
合計ジャッジ時間 126,673 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
61,672 KB
testcase_01 AC 28 ms
31,040 KB
testcase_02 AC 27 ms
61,132 KB
testcase_03 AC 28 ms
61,488 KB
testcase_04 AC 116 ms
61,720 KB
testcase_05 AC 27 ms
31,172 KB
testcase_06 AC 31 ms
61,212 KB
testcase_07 AC 28 ms
30,716 KB
testcase_08 AC 32 ms
60,164 KB
testcase_09 AC 28 ms
61,260 KB
testcase_10 AC 28 ms
61,604 KB
testcase_11 AC 29 ms
61,096 KB
testcase_12 AC 28 ms
61,520 KB
testcase_13 AC 32 ms
61,312 KB
testcase_14 AC 31 ms
61,188 KB
testcase_15 AC 31 ms
61,188 KB
testcase_16 AC 28 ms
60,900 KB
testcase_17 AC 29 ms
61,524 KB
testcase_18 AC 28 ms
30,852 KB
testcase_19 AC 30 ms
61,220 KB
testcase_20 AC 28 ms
30,840 KB
testcase_21 AC 34 ms
24,060 KB
testcase_22 AC 28 ms
24,120 KB
testcase_23 AC 31 ms
24,048 KB
testcase_24 AC 30 ms
23,920 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 100 ms
24,572 KB
testcase_46 AC 27 ms
23,956 KB
testcase_47 AC 238 ms
24,980 KB
testcase_48 AC 27 ms
23,936 KB
testcase_49 AC 267 ms
61,872 KB
権限があれば一括ダウンロードができます

ソースコード

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