CODE FESTIVAL 2016 Final

Submission #994844

Source codeソースコード

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const int MX = 210;
const ll MOD = 1e9 + 7;

int n, m;
char s[MX][MX];
int en[MX][MX];

int cc0[MX];
int cc1[MX];
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> s[i];
	ll ans = 1;
	int fl1 = 0;
	int fl2 = 0;
	for (int i = 0; i * 2 < n; ++i)
		for (int j = 0; j * 2 < m; ++j) {
			if (i * 2 == n - 1 && j * 2 == m - 1)
				continue;
			if (i * 2 == n - 1) {
				if (s[i][j] != s[i][m - 1 - j])
					fl1 = 1;
			}
			else if (j * 2 == m - 1) {
				if (s[i][j] != s[n - 1 - i][j])
					fl2 = 1;
			}
			else {
				vector<char> vv;
				vv.push_back(s[i][j]);
				vv.push_back(s[n - 1 - i][j]);
				vv.push_back(s[n - 1 - i][m - 1 - j]);
				vv.push_back(s[i][m - 1 - j]);
				sort(vv.begin(), vv.end());
				if (vv[0] == vv[3]) {
					en[i][j] = 1;
				}
				else if (vv[0] == vv[2] || vv[1] == vv[3]) {
					en[i][j] = 1;
					ans = (ans * 4) % MOD;
				}
				else if (vv[0] == vv[1] && vv[2] == vv[3]) {
					en[i][j] = 1;
					ans = (ans * 6) % MOD;
				}
				else if (vv[0] == vv[1] || vv[1] == vv[2] || vv[2] == vv[3]) {
					en[i][j] = 1;
					ans = (ans * 12) % MOD;
				}
				else {
					ans = (ans * 12) % MOD;
				}
			}
		}
	if (fl1)
		ans = (ans * 2) % MOD;
	if (fl2)
		ans = (ans * 2) % MOD;
	n = n / 2;
	m = m / 2;
	int fl = 1;
	while (fl) {
		fl = 0;
		for (int i = 0; i < n; ++i)
			cc0[i] = 0;
		for (int i = 0; i < m; ++i)
			cc1[i] = 0;
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
				if (!en[i][j])
					++cc0[i], ++cc1[j];
		for (int i = 0; i < n; ++i) {
			if (cc0[i] >= 2)
				continue;
			if (cc0[i] == 1)
				ans = (ans * 2) % MOD;
			fl = 1;
			for (int j = i + 1; j < n; ++j)
				for (int k = 0; k < m; ++k)
					en[j - 1][k] = en[j][k];
			--n;
			break;
		}
		if (fl)
			continue;
		for (int i = 0; i < m; ++i) {
			if (cc1[i] >= 2)
				continue;
			if (cc1[i] == 1)
				ans = (ans * 2) % MOD;
			fl = 1;
			for (int j = i + 1; j < m; ++j)
				for (int k = 0; k < n; ++k)
					en[k][j - 1] = en[k][j];
			--m;
			break;
		}
		if (fl)
			continue;
	}
	if (n > 0 && m > 0) {
		int cc = (n + m - 1);
		for (int j = 0; j < cc; ++j)
			ans = (ans * 2) % MOD;
	}
	cout << ans << "\n";
	return 0;
}


Submission

Task問題 I - Reverse Grid
User nameユーザ名 LHiC
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1900
Source lengthソースコード長 2637 Byte
File nameファイル名
Exec time実行時間 6 ms
Memory usageメモリ使用量 384 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
all 1900 / 1900 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 3 ms 256 KB
01-02.txt AC 3 ms 256 KB
01-03.txt AC 3 ms 256 KB
01-04.txt AC 3 ms 256 KB
01-05.txt AC 2 ms 256 KB
01-06.txt AC 3 ms 256 KB
01-07.txt AC 3 ms 256 KB
01-08.txt AC 3 ms 256 KB
01-09.txt AC 3 ms 256 KB
01-10.txt AC 6 ms 384 KB
01-11.txt AC 6 ms 384 KB
01-12.txt AC 6 ms 384 KB
01-13.txt AC 6 ms 384 KB
01-14.txt AC 3 ms 256 KB
01-15.txt AC 3 ms 384 KB
01-16.txt AC 5 ms 384 KB
01-17.txt AC 5 ms 384 KB
01-18.txt AC 5 ms 384 KB
01-19.txt AC 5 ms 384 KB
01-20.txt AC 5 ms 384 KB
01-21.txt AC 5 ms 384 KB
01-22.txt AC 3 ms 256 KB
01-23.txt AC 4 ms 384 KB
01-24.txt AC 5 ms 384 KB
01-25.txt AC 5 ms 384 KB
01-26.txt AC 5 ms 384 KB
01-27.txt AC 3 ms 256 KB
01-28.txt AC 3 ms 256 KB
01-29.txt AC 3 ms 384 KB
01-30.txt AC 3 ms 256 KB
01-31.txt AC 5 ms 384 KB
01-32.txt AC 5 ms 384 KB
01-33.txt AC 5 ms 384 KB
01-34.txt AC 5 ms 384 KB
01-35.txt AC 5 ms 384 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB