Submission #1004514


Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt() : x(0) {}
	ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;

struct UnionFind {
	vector<int> data;
	void init(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if(x != y) {
			if(data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

int main() {
	int H; int W;
	while(~scanf("%d%d", &H, &W)) {
		vector<string> S(H);
		rep(i, H) {
			char buf[201];
			scanf("%s", buf);
			S[i] = buf;
		}
		auto revEqual = [](string s) -> bool {
			return s == string(s.rbegin(), s.rend());
		};
		auto countNum = [](string s) -> int {
			const int fact[5] = { 1, 1, 2, 6, 24 };
			map<char, int> cnt;
			for(char c : s) ++ cnt[c];
			int res = fact[s.size()];
			for(auto &&p : cnt)
				res /= fact[p.second];
			return res;
		};
		mint ans = 1;
		if(H % 2 == 1) {
			ans *= revEqual(S[H / 2]) ? 1 : 2;
			S.erase(S.begin() + H / 2);
			-- H;
		}
		if(W % 2 == 1) {
			string col;
			rep(i, H) {
				col += S[i][W / 2];
				S[i].erase(S[i].begin() + W / 2);
			}
			ans *= revEqual(col)  ? 1 : 2;
			-- W;
		}
		UnionFind uf;
		uf.init(H / 2 + W / 2);
		rep(i, H / 2) rep(j, W / 2) {
			string group;
			group += S[i][j];
			group += S[H - 1 - i][j];
			group += S[i][W - 1 - j];
			group += S[H - 1 - i][W - 1 - j];
			int num = countNum(group);
			ans *= num == 24 ? num / 2 : num;
			if(num == 24)
				uf.unionSet(i, H / 2 + j);
		}
		int ways = H / 2 + W / 2;
		rep(i, H / 2 + W / 2)
			ways -= uf.root(i) == i;
		rep(i, ways)
			ans *= 2;
		printf("%d\n", ans.get());
	}
	return 0;
}

Submission Info

Submission Time
Task I - Reverse Grid
User anta
Language C++14 (GCC 5.4.1)
Score 1900
Code Size 3184 Byte
Status AC
Exec Time 8 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", buf);
                    ^

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1900 / 1900
Status
AC × 2
AC × 37
Set Name Test Cases
sample sample-01.txt, sample-02.txt
all 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
Case Name Status Exec Time Memory
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 3 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 256 KB
01-11.txt AC 6 ms 256 KB
01-12.txt AC 6 ms 256 KB
01-13.txt AC 6 ms 256 KB
01-14.txt AC 4 ms 256 KB
01-15.txt AC 4 ms 256 KB
01-16.txt AC 7 ms 256 KB
01-17.txt AC 7 ms 256 KB
01-18.txt AC 7 ms 256 KB
01-19.txt AC 7 ms 256 KB
01-20.txt AC 7 ms 256 KB
01-21.txt AC 7 ms 256 KB
01-22.txt AC 3 ms 256 KB
01-23.txt AC 5 ms 256 KB
01-24.txt AC 7 ms 256 KB
01-25.txt AC 7 ms 256 KB
01-26.txt AC 7 ms 256 KB
01-27.txt AC 3 ms 256 KB
01-28.txt AC 3 ms 256 KB
01-29.txt AC 3 ms 256 KB
01-30.txt AC 4 ms 256 KB
01-31.txt AC 8 ms 256 KB
01-32.txt AC 7 ms 256 KB
01-33.txt AC 7 ms 256 KB
01-34.txt AC 7 ms 256 KB
01-35.txt AC 7 ms 256 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB