結果

問題 No.753 最強王者決定戦
ユーザー xuzijian629xuzijian629
提出日時 2018-11-09 22:53:57
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 264 ms / 1,000 ms
コード長 1,985 bytes
コンパイル時間 2,815 ms
コンパイル使用メモリ 218,996 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2024-11-21 06:37:35
合計ジャッジ時間 4,110 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 250 ms
8,320 KB
testcase_01 AC 264 ms
8,576 KB
testcase_02 AC 197 ms
7,168 KB
testcase_03 AC 244 ms
8,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

int main() {
    vvi win(16, vi(16));
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) {
            int k;
            cin >> k;
            if (i < j) {
                if (k == 1) {
                    win[i][j] = 1;
                    win[j][i] = 0;
                } else {
                    win[i][j] = 0;
                    win[j][i] = 1;
                }
            }
        }
    }

    using vm = vector<map<i64, i64>>;
    vector<vm> dp(5, vm(16));
    for (int i = 0; i < 16; i++) {
        dp[0][i][1 << i] = 1;
    }

    for (int r = 1; r < 5; r++) {
        for (int i = 0; i < 16; i++) {
            for (int j = i + 1; j < 16; j++) {
                for (auto& p: dp[r - 1][i]) {
                    if (r < 4) {
                        for (auto& q: dp[r - 1][j]) {
                            if (p.first & q.first) continue;
                            if (win[i][j]) {
                                dp[r][i][p.first | q.first] += p.second * q.second;
                            } else {
                                dp[r][j][p.first | q.first] += p.second * q.second;
                            }
                        }
                    } else {
                        int k = ((1 << 16) - 1) ^ p.first;
                        if (dp[r - 1][j].count(k)) {
                            if (win[i][j]) {
                                dp[r][i][p.first | k] += p.second * dp[r - 1][j][k];
                            } else {
                                dp[r][j][p.first | k] += p.second * dp[r - 1][j][k];
                            }
                        }
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < 16; i++) {
        cout << 32768 * dp[4][i][(1 << 16) - 1] << endl;
    }
}
0