Submission #994081
Source Code Expand
#include <cstdio> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <cstring> #include <string> #include <cmath> #include <cstdlib> #include <iostream> using namespace std; #define MOD 1000000007 #define ADD(X,Y) ((X) = ((X) + (Y)) % MOD) typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec; int H, W; vector<string> S; bool pal[110][110]; int cnt[110][110]; int fact[] = { 1, 1, 2, 6, 24 }; int uf[303030]; int root(int p) { return uf[p] < 0 ? p : (uf[p] = root(uf[p])); } bool join(int p, int q) { p = root(p); q = root(q); if (p == q) return false; uf[p] += uf[q]; uf[q] = p; return true; } int pohe(vector<char> ch) { int ret = 24; for (int i = 0; i < ch.size(); ++i) { int app = 0; for (int j = 0; j < ch.size(); ++j) { if (ch[i] == ch[j]) { ++app; if (i < j) goto nxt; } } ret /= fact[app]; nxt: continue; } return ret; } int main() { scanf("%d%d", &H, &W); for (int i = 0; i < H; ++i) { char in[220]; scanf("%s", in); S.push_back(string(in)); } i64 mult = 1; if (S.size() % 2 == 1) { string tg = S[S.size() / 2]; string tg2 = tg; reverse(tg2.begin(), tg2.end()); if (tg != tg2) mult *= 2; S.erase(S.begin() + (S.size() / 2)); } if (S.size() == 0) { printf("%lld\n", mult); return 0; } H = S.size(); if (S[0].size() % 2 == 1) { string tg; for (int i = 0; i < H; ++i) { tg.push_back(S[i][S[0].size() / 2]); S[i].erase(S[i].begin() + (S[0].size() / 2)); } string tg2 = tg; reverse(tg2.begin(), tg2.end()); if (tg != tg2) mult *= 2; } if (S[0].size() == 0) { printf("%lld\n", mult); return 0; } H = S.size(); W = S[0].size(); i64 ret = 1; for (int i = 0; i < H / 2; ++i) { for (int j = 0; j < W / 2; ++j) { vector<char> ch; ch.push_back(S[i][j]); ch.push_back(S[H - 1 - i][j]); ch.push_back(S[i][W - 1 - j]); ch.push_back(S[H - 1 - i][W - 1 - j]); int waf = pohe(ch); if (waf == 24) { pal[i][j] = true; cnt[i][j] = 12; } else { pal[i][j] = false; cnt[i][j] = waf; } } } for (int i = 0; i < 5000; ++i) uf[i] = -1; int rem = 0; for (int i = 0; i < H / 2; ++i) { for (int j = 0; j < W / 2; ++j) { if (pal[i][j]) { if (join(i, j + H / 2)) ++rem; } ret = ret * cnt[i][j] % MOD; } } while (rem--) ret = ret * 2 % MOD; ret = ret * mult % MOD; printf("%lld\n", ret); return 0; }
Submission Info
Submission Time | |
---|---|
Task | I - Reverse Grid |
User | semiexp |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 2573 Byte |
Status | AC |
Exec Time | 5 ms |
Memory | 512 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:64:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &H, &W); ^ ./Main.cpp:67:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s", in); ^
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 | 5 ms | 384 KB |
01-11.txt | AC | 4 ms | 512 KB |
01-12.txt | AC | 5 ms | 384 KB |
01-13.txt | AC | 5 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 | 384 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 |