結果

問題 No.753 最強王者決定戦
ユーザー ats5515ats5515
提出日時 2018-11-09 22:07:57
言語 C++11
(gcc 11.4.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,509 bytes
コンパイル時間 663 ms
コンパイル使用メモリ 84,116 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-21 05:59:24
合計ジャッジ時間 1,635 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int C(long long int)’:
main.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
   57 | }
      | ^

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
int dp[1 << 16];
int A[16][16];
int sz = 0;
vector<int> loser;
vector<int> winner;
int z = 0;
int xx;
int Y[16];
void dfs(int a) {

	if (a == (int)winner.size()) {
		dp[xx] += dp[z];
	}
	else {
		for (int k = 0; k < loser.size(); k++) {
			if (Y[loser[k]] == 1) {
				if (A[winner[a]][loser[k]] == 1) {
					Y[loser[k]] = 0;
					z |= (1 << loser[k]);
					dfs(a + 1);
					Y[loser[k]] = 1;
					z ^= (1 << loser[k]);
				}
			}
		}
	}
}
int C(int x) {
	winner.clear();
	loser.clear();
	for (int i = 0; i < 16; i++) {
		if (x & (1 << i)) {
			winner.push_back(i);
			Y[i] = 0;
		}
		else {
			loser.push_back(i);
			Y[i] = 1;
		}
	}
	z = x;
	xx = x;
	dfs(0);
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int res = 0;
	for (int i = 0; i < 16; i++) {
		for (int j = 0; j < 16; j++) {
			cin >> A[i][j];
		}
	}
	for (int i = 0; i < 16; i++) {
		for (int j = 0; j < 16; j++) {
			if (i > j) {
				A[i][j] = -A[j][i];
			}
		}
	}
	dp[(1 << 16) - 1] = (1 << 15);
	for (int j = 0; j < 4; j++) {
		int k = (8 >> j);
		//cerr << k << endl;
		for (int x = (1 << k) - 1; x < (1 << 16); ) {
			C(x);
			int t = x | (x - 1);
			x = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(x) + 1));
		}
	}
	for (int i = 0; i < 16; i++) {
		cout << dp[1 << i] << endl;
	}
}
0