Submission #3636838

---

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) | (ll)S_[rx][j];
            y = (y << 5LL) | (ll)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);

    if (H % 2) {
        do {
            rep(i,hl) hlpat[i] = hh + i;
            do {
                int a=0, b=0;
                for (int i=0; i<H; ++i){
                    if (!hhpat[i]) hpat[a++] = i;
                    else           hpat[hlpat[b++]] = i;
                }
                if (sub(hpat)) return true;

            } while (next_permutation(ALL(hlpat)));
        } while (next_permutation(hhpat.begin(), hhpat.end()));
    } else {
        do {
            rep(i,hl) hlpat[i] = hh + i;
            do {
                int a=1, b=0;
                for (int i=1; i<H; ++i){
                    if (!hhpat[i]) hpat[a++] = i;
                    else           hpat[hlpat[b++]] = i;
                }
                if (sub(hpat)) return true;

            } 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

Judge Result