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
2016-12-01 15:57:41+0900
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
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