結果
問題 | No.753 最強王者決定戦 |
ユーザー | KPCCoiL |
提出日時 | 2019-03-02 12:29:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 985 ms / 1,000 ms |
コード長 | 1,679 bytes |
コンパイル時間 | 856 ms |
コンパイル使用メモリ | 78,108 KB |
実行使用メモリ | 11,792 KB |
最終ジャッジ日時 | 2024-06-23 12:24:57 |
合計ジャッジ時間 | 6,153 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 985 ms
11,584 KB |
testcase_01 | AC | 965 ms
11,792 KB |
testcase_02 | AC | 954 ms
11,652 KB |
testcase_03 | AC | 946 ms
11,516 KB |
ソースコード
#include <iostream> #include <array> #include <algorithm> #include <vector> using namespace std; constexpr int fighters = 16; inline int to_bits(array<bool, fighters> const& bits) { int result = 0; for (int i = 0; i < fighters; i++) result |= bits[i] << i; return result; } array<array<long long, (1 << fighters)>, fighters> dp; int main() { array<array<int, fighters>, fighters> result; for (auto& row : result) for (auto& v : row) cin >> v; for (int i = 0; i < fighters; i++) for (int j = 0; j < i; j++) result[i][j] = -result[j][i]; for (auto& row : dp) for (auto& v : row) v = 0; for (int i = 0; i < fighters; i++) dp[i][1 << i] = 1; for (int i = 0; i <= 3; i++) { int high_digit = 1 << i; array<bool, fighters> a; vector<bool> b(fighters - high_digit); fill(rbegin(a), rbegin(a) + high_digit, 1); fill(rbegin(a) + high_digit, rend(a), 0); fill(rbegin(b), rbegin(b) + high_digit, 1); do { do { int n = to_bits(a), m = 0, b_idx = 0; for (int j = 0; j < fighters; j++) { if (n & (1 << j)) continue; m |= b[b_idx] << j; b_idx++; } for (int j = 0; j < fighters; j++) { for (int k = 0; k < fighters; k++) { if (j == k) continue; if (result[j][k] > 0) dp[j][n | m] += dp[j][n] * dp[k][m]; else dp[k][n | m] += dp[j][n] * dp[k][m]; } } } while (next_permutation(begin(a), end(a))); } while (next_permutation(begin(b), end(b))); } for (int i = 0; i < fighters; i++) cout << dp[i][(1 << 16) - 1] << endl; }