Submission #3637094

---

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(), paircnt = 0;
    assert(m % 2 == 0);
    vector<bool> used(m, false);
    repC2(i,j,m){
        if (used[i] || used[j]) continue;
        if (xs[i] == ys[j]){
            ++paircnt;
            used[i] = used[j] = true;
        }
    }
    return (paircnt == m/2);
}


bool solve(){
    S_.resize(H);
    rep(i,H){
        S_[i].resize(W);
        rep(j,W) S_[i][j] = S[i][j] - 'a';
    }

    if (H % 2) {
        vi b(H);
        queue<pair<int,vi>> tmp;
        vi iota(H); rep(i,H) iota[i] = i;

        for (int j=0; j<H; ++j) {
            swap(iota[0], iota[j]);
            tmp.push(cons(1, iota));
            swap(iota[0], iota[j]);
        }
        while (!tmp.empty()) {
            auto t = tmp.front(); tmp.pop();
            int ix = t.first;
            vi a = t.second;
            if (ix == H) {
                b[H/2] = a[0];
                for (int i=0; i<H/2; ++i) {
                    b[i] = a[1+i*2];
                    b[H-1-i] = a[1+i*2+1];
                }
                if (sub(b)) return true;
                continue;
            }

            for (int iy=ix+1; iy<H; ++iy) {
                swap(a[ix], a[iy]);
                tmp.push(cons(ix+2, a));
                swap(a[ix], a[iy]);
            }
        }

    } else {
        vi b(H);

        queue<pair<int,vi>> tmp;
        vi iota(H); rep(i,H) iota[i] = i;
        tmp.push(cons(0,iota));
        while (!tmp.empty()) {
            auto t = tmp.front(); tmp.pop();
            int ix = t.first;
            vi a = t.second;
            if (ix == H) {
                for (int i=0; i<H/2; ++i) {
                    b[i] = a[i*2];
                    b[H-1-i] = a[i*2+1];
                }
                if (sub(b)) return true;
                continue;
            }

            for (int iy=ix+1; iy<H; ++iy) {
                swap(a[ix], a[iy]);
                tmp.push(cons(ix+2, a));
                swap(a[ix], a[iy]);
            }
        }
    }
    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