Submission #3636638
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define NDEBUG
#include <cassert>
typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n) for(int var=0;var<(n);++var)
#define rep1(var,n) for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n) for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e) ((s).find(e)!=(s).end())
#define mset(arr,val) memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair
int maximum_match_count(vector<pair<int, int> >& possible_pairs) {
const int infty = 987654321;
int M = possible_pairs.size();
if (M <= 1) return M;
set<int> _part1, _part2;
for (int i=0; i<M; ++i) {
int p1 = possible_pairs[i].first, p2 = possible_pairs[i].second;
_part1.insert(p1);
_part2.insert(p2);
}
vector<int> part1(ALL(_part1)), part2(ALL(_part2));
int P1 = part1.size(), P2 = part2.size();
map<int, int> part1_map, part2_map;
for (int i=0; i<P1; ++i) part1_map[part1[i]] = i;
for (int i=0; i<P2; ++i) part2_map[part2[i]] = i;
int w = 1 + P1 + P2 + 1;
vector<vector<int> > capacity(w, vector<int>(w, 0));
for (int i=0; i<P1; ++i) {
capacity[0][1+i] = 1;
}
for (int i=0; i<M; ++i) {
int p1 = part1_map[possible_pairs[i].first];
int p2 = part2_map[possible_pairs[i].second];
assert((0 <= p1 && p1 < P1) && (0 <= p2 && p2 < P2));
capacity[1+p1][1+P1+p2] = 1;
}
for (int i=0; i<P2; ++i) {
capacity[1+P1+i][1+P1+P2] = 1;
}
int s = 0, t = w-1;
vector<vector<int> > resid(w, vector<int>(w, 0));
for (int j=0; j<w-1; ++j) {
for (int k=j+1; k<w; ++k) {
resid[j][k] = capacity[j][k];
resid[k][j] = 0;
}
}
int total = 0;
for (total=0; ; ++total) {
bool another_way = false;
vector<int> prev(w, infty);
queue<pair<int, int> > q;
q.push(pair<int, int>(s, -1));
while (!q.empty()) {
pair<int, int> p = q.front();
int node = p.first, prev_node = p.second;
q.pop();
prev[node] = prev_node;
if (node == t) { another_way = true; break; }
rep(i, w) {
if (resid[node][i] == 0) continue;
if (prev[i] < infty) continue;
q.push(pair<int, int>(i, node));
}
}
if (!another_way) {
return total;
}
for (int node=t; node!=s; node=prev[node]) {
int prev_node = prev[node];
resid[prev_node][node]--;
resid[node][prev_node]++;
}
}
return 0;
}
int H, W;
vector<string> S;
vvi S_;
bool sub(vi& hpat){
vector<ll> xs, ys;
map<ll,int> same;
rep(j,W){
ll x = 0, y = 0;
rep(i,H){
int rx = hpat[i], ry = hpat[H-1-i];
x = (x << 5LL) | S_[rx][j];
y = (y << 5LL) | S_[ry][j];
}
if (x == y) same[x]++;
else { xs.pb(x); ys.pb(y); }
}
int unpaired = 0;
for (auto p: same){
ll x = p.first; int cnt = p.second;
if (cnt % 2) unpaired++;
}
if (unpaired != W%2) return false;
vector<ii> pairs;
int m = xs.size();
assert(m % 2 == 0);
repC2(i,j,m){
if (xs[i] == ys[j])
pairs.pb(ii(i,j));
}
int mmc = maximum_match_count(pairs);
return (mmc == m/2);
}
bool solve(){
S_.resize(H);
rep(i,H){
S_[i].resize(W);
rep(j,W) S_[i][j] = S[i][j] - 'a';
}
int hh = H/2, hl = H-hh;
vi hhpat(H, 1);
rep(i,hh) hhpat[i] = 0;
vi hlpat(hl);
vi hpat(H, 0);
do {
rep(i,hl) hlpat[i] = i;
do {
int a=0, b=0;
for (int i=1;i<H;++i){
if (!hhpat[i]) hpat[i] = ++a;
else hpat[i] = hh + hlpat[b++];
}
if (sub(hpat)) return true;
if (H%2) {
swap(hpat[0], hpat[H/2]);
if (sub(hpat)) return true;
swap(hpat[0], hpat[H/2]);
}
} while (next_permutation(ALL(hlpat)));
} while (next_permutation(hhpat.begin()+1, hhpat.end()));
return false;
}
int main() {
cin >> H >> W;
S.resize(H); rep(i,H) cin >> S[i];
cout << (solve() ? "YES":"NO") << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Symmetric Grid |
User |
naoya_t |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5215 Byte |
Status |
WA |
Exec Time |
331 ms |
Memory |
384 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 100.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 4.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 5.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
1.txt |
AC |
1 ms |
256 KB |
10.txt |
AC |
1 ms |
256 KB |
100.txt |
AC |
2 ms |
256 KB |
11.txt |
AC |
14 ms |
256 KB |
12.txt |
AC |
13 ms |
256 KB |
13.txt |
AC |
7 ms |
256 KB |
14.txt |
WA |
296 ms |
256 KB |
15.txt |
AC |
208 ms |
256 KB |
16.txt |
AC |
330 ms |
256 KB |
17.txt |
AC |
250 ms |
256 KB |
18.txt |
WA |
292 ms |
256 KB |
19.txt |
AC |
254 ms |
256 KB |
2.txt |
AC |
1 ms |
256 KB |
20.txt |
WA |
329 ms |
256 KB |
21.txt |
AC |
294 ms |
256 KB |
22.txt |
AC |
289 ms |
256 KB |
23.txt |
AC |
260 ms |
256 KB |
24.txt |
WA |
264 ms |
256 KB |
25.txt |
WA |
325 ms |
256 KB |
26.txt |
AC |
284 ms |
384 KB |
27.txt |
AC |
284 ms |
256 KB |
28.txt |
AC |
328 ms |
256 KB |
29.txt |
WA |
298 ms |
256 KB |
3.txt |
AC |
1 ms |
256 KB |
30.txt |
WA |
254 ms |
256 KB |
31.txt |
AC |
254 ms |
256 KB |
32.txt |
WA |
324 ms |
256 KB |
33.txt |
AC |
284 ms |
256 KB |
34.txt |
AC |
228 ms |
256 KB |
35.txt |
AC |
297 ms |
256 KB |
36.txt |
AC |
8 ms |
256 KB |
37.txt |
AC |
161 ms |
256 KB |
38.txt |
AC |
287 ms |
256 KB |
39.txt |
AC |
2 ms |
256 KB |
4.txt |
AC |
1 ms |
256 KB |
40.txt |
AC |
287 ms |
256 KB |
41.txt |
AC |
254 ms |
256 KB |
42.txt |
AC |
294 ms |
256 KB |
43.txt |
AC |
331 ms |
256 KB |
44.txt |
AC |
268 ms |
256 KB |
45.txt |
AC |
26 ms |
256 KB |
46.txt |
AC |
81 ms |
256 KB |
47.txt |
AC |
5 ms |
256 KB |
48.txt |
AC |
241 ms |
256 KB |
49.txt |
AC |
291 ms |
256 KB |
5.txt |
AC |
1 ms |
256 KB |
50.txt |
AC |
220 ms |
256 KB |
51.txt |
WA |
325 ms |
256 KB |
52.txt |
AC |
330 ms |
256 KB |
53.txt |
AC |
329 ms |
256 KB |
54.txt |
AC |
1 ms |
256 KB |
55.txt |
AC |
1 ms |
256 KB |
56.txt |
AC |
329 ms |
256 KB |
6.txt |
AC |
1 ms |
256 KB |
7.txt |
AC |
1 ms |
256 KB |
8.txt |
AC |
1 ms |
256 KB |
9.txt |
AC |
1 ms |
256 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
19 ms |
256 KB |