結果

問題 No.452 横着者のビンゴゲーム
コンテスト
ユーザー pekempey
提出日時 2016-12-03 04:23:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 244 ms / 3,000 ms
コード長 1,540 bytes
コンパイル時間 1,876 ms
コンパイル使用メモリ 178,648 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-28 22:05:24
合計ジャッジ時間 4,816 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0