#134691 (C++14) No.452 横着者のビンゴゲーム

提出ソース

結果

問題	No.452 横着者のビンゴゲーム
ユーザー	pekempey
提出日時	2016-12-03 04:23:48
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	270 ms / 3,000 ms
コード長	1,540 bytes
コンパイル時間	1,945 ms
コンパイル使用メモリ	178,204 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-05-06 14:48:39
合計ジャッジ時間	5,581 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	270 ms 5,376 KB
testcase_15	AC	261 ms 5,376 KB
testcase_16	AC	164 ms 5,376 KB
testcase_17	AC	30 ms 5,376 KB
testcase_18	AC	25 ms 5,376 KB
testcase_19	AC	22 ms 5,376 KB
testcase_20	AC	23 ms 5,376 KB
testcase_21	AC	55 ms 5,376 KB
testcase_22	AC	20 ms 5,376 KB
testcase_23	AC	98 ms 5,376 KB
testcase_24	AC	20 ms 5,376 KB
testcase_25	AC	10 ms 5,376 KB
testcase_26	AC	63 ms 5,376 KB
testcase_27	AC	51 ms 5,376 KB
testcase_28	AC	28 ms 5,376 KB
testcase_29	AC	22 ms 5,376 KB
testcase_30	AC	71 ms 5,376 KB
testcase_31	AC	14 ms 5,376 KB
testcase_32	AC	14 ms 5,376 KB
testcase_33	AC	38 ms 5,376 KB
testcase_34	AC	30 ms 5,376 KB
testcase_35	AC	32 ms 5,376 KB
testcase_36	AC	12 ms 5,376 KB
testcase_37	AC	15 ms 5,376 KB
testcase_38	AC	225 ms 5,376 KB
testcase_39	AC	159 ms 5,376 KB
testcase_40	AC	159 ms 5,376 KB
testcase_41	AC	160 ms 5,376 KB
testcase_42	AC	159 ms 5,376 KB
testcase_43	AC	161 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> v1;
typedef vector<v1> v2;
typedef vector<v2> v3;

// #define getchar getchar_unlocked

int in() {
	int n, c;
	while ((c = getchar()) < '0') {
		assert(c != EOF);
	}
	n = c - '0';
	while ((c = getchar()) >= '0') {
		n = n * 10 + c - '0';
	}
	return n;
}

void iterate(v3 &c, int k, function<void(v1 &)> f) {
	int n = c[0].size();
	v2 &a = c[k];
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			v[j] = a[i][j];
		}
		f(v);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			v[j] = a[j][i];
		}
		f(v);
	}
	for (int i = 0; i < n; i++) {
		v[i] = a[i][i];
	}
	f(v);
	for (int i = 0; i < n; i++) {
		v[i] = a[n - 1 - i][i];
	}
	f(v);
}

int main() {
	int n = in(), m = in();
	v3 c(m, v2(n, v1(n)));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				c[i][j][k] = in();
			}
		}
	}
	int ans = INT_MAX;
	vector<int> buf(2 * n);
	vector<bool> used(100000);
	for (int i = 0; i < m; i++) {
		for (int j = i + 1; j < m; j++) {
			iterate(c, i, [&](v1 &x) {
				iterate(c, j, [&](v1 &y) {
					int cnt = 0;
					for (int e : x) {
						if (!used[e]) {
							cnt++;
						}
						used[e] = true;
					}
					for (int e : y) {
						if (!used[e]) {
							cnt++;
						}
						used[e] = true;
					}
					for (int e : x) {
						used[e] = false;
					}
					for (int e : y) {
						used[e] = false;
					}
					ans = min(ans, cnt - 1);
				});
			});
		}
	}
	cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード