結果

問題 No.753 最強王者決定戦
ユーザー KPCCoiLKPCCoiL
提出日時 2019-03-02 12:20:56
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,526 bytes
コンパイル時間 571 ms
コンパイル使用メモリ 72,520 KB
実行使用メモリ 25,200 KB
最終ジャッジ日時 2024-06-23 12:20:11
合計ジャッジ時間 5,082 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <array>
#include <algorithm>

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, b;
    for (int j = 0; j < fighters; j++)
      a[j] = b[j] = ((fighters - j - 1 < high_digit) ? 1 : 0);

    do {
      do {
        int n = to_bits(a),
            m = to_bits(b);
        // cout << n << ' ' << m << endl;
        if ((n & m) != 0) continue;
        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;
}
0