Submission #19305053

---

Source Code Expand

//int good_vec(vi a){
//    map<int,int> cnt;
//    for(int x : a)
//        cnt[x] ^= 1;
//    int s = 0;
//    for(auto _ : cnt)
//        s += _.Y;
//    return s <= 1;
//}
//bool solve(vvi grid){
//    int n = sz(grid);
//    int half = n/2;
//    rep(i,n)
//        sort(all(grid[i]));
//    sort(all(grid));
//    rep(bm,1<<n){
//        if(__builtin_popcount(bm) != half) continue;
//        vvi tmp,order;
//        rep(i,n)
//            if(bm&(1<<i))
//                tmp.pb(grid[i]);
//            else
//                order.pb(grid[i]);
//        do{
//            bool ok = true;
//            rep(i,half)
//                if(tmp[i] != order[i])
//                    ok = false;
//            if(ok)
//                return true;
//
//        }while(next_permutation(all(order)));
//    }
//    return false;
//}
//string __(){
//    int h,w;
//    cin >> h >> w;
//    vvi grid(h,vi(w));
//    rep(i,h)
//        rep(j,w){
//            char c;
//            cin >> c;
//            grid[i][j] = c-'a';
//        }
//    if(!solve(grid))
//        return "NO";
//    {
//        vvi tmp(w,vi(h));
//        rep(i,h)
//            rep(j,w){
//                tmp[j][i] = grid[i][j];
//            }
//        grid = tmp;
//    }
//    if(!solve(grid))
//        return "NO";
//    return "YES";
//}
//
#include <map>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define REP_ZERO_INT(i,r) for(int i = 0; i < (r); ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT,REP_ZERO_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define Y second
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 istream& read(T, T, istream& = cin);
int good_vec(vi a){
    map<int,int> cnt;
    for(int x : a)
        cnt[x] ^= 1;
    int s = 0;
    for(auto _ : cnt)
        s += _.Y;
    return s <= 1;
}
bool solve(vvi grid){
    int n = sz(grid);
    int half = n/2;
    rep(i,n)
        sort(all(grid[i]));
    sort(all(grid));
    rep(bm,1<<n){
        if(__builtin_popcount(bm) != half) continue;
        vvi tmp,order;
        rep(i,n)
            if(bm&(1<<i))
                tmp.pb(grid[i]);
            else
                order.pb(grid[i]);
        do{
            bool ok = true;
            rep(i,half)
                if(tmp[i] != order[i])
                    ok = false;
            if(ok)
                return true;

        }while(next_permutation(all(order)));
    }
    return false;
}
string __(){
    int h,w;
    cin >> h >> w;
    vvi grid(h,vi(w));
    rep(i,h)
        rep(j,w){
            char c;
            cin >> c;
            grid[i][j] = c-'a';
        }
    if(!solve(grid))
        return "NO";
    {
        vvi tmp(w,vi(h));
        rep(i,h)
            rep(j,w){
                tmp[j][i] = grid[i][j];
            }
        grid = tmp;
    }
    if(!solve(grid))
        return "NO";
    return "YES";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        cout << __() << '\n';
}

Submission Info

Judge Result