Submission #19305532


Source Code Expand

Copy
//bool check(vvi grid){
//    int h = sz(grid);
//    int w = sz(grid[0]);
//    {
//        vvi tmp(w,vi(h));
//        rep(i,h)
//            rep(j,w){
//                tmp[j][i] = grid[i][j];
//            }
//        grid = tmp;
//    }
//    swap(h,w);
//    multiset<vi> rows;
//    rep(i,h)
//        rows.insert(grid[i]);
//    while(sz(rows) >= 2){
//        vi a = min(rows);
//        rows.erase(rows.begin());
//        vi b = a;
//        reverse(all(b));
//        auto it = rows.find(b);
//        if(it != rows.end())
//            rows.erase(it);
//        else{
//            if(a != b)
//                return false;
//        }
//    }
//    if(!rows.empty()){
//        vi a = min(rows);
//        vi b = a;
//        reverse(all(b));
//        if(a != b)
//            return false;
//    }
//    return true;
//}
//bool solve(vvi grid){
//    int n = sz(grid);
//    int half = n/2;
//    sort(all(grid));
//    rep(bm,1<<n){
//        if(__builtin_popcount(bm) != half) continue;
//        vvi tmp;
//        rep(i,n)
//            if(bm&(1<<i))
//                tmp.pb(grid[i]);
//        rep(i,n)
//            if(!(bm&(1<<i)))
//                tmp.pb(grid[i]);
//        do{
//            if(check(tmp))
//                return true;
//
//        }while(next_permutation(tmp.begin()+half,tmp.end()));
//    }
//    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 <set>
#include <iomanip>
#include <algorithm>
#include <cassert>
#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 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);
T1 T min(const multiset<T>& s){
    assert(!s.empty());
    return *s.begin();
}
bool check(vvi grid){
    int h = sz(grid);
    int w = sz(grid[0]);
    {
        vvi tmp(w,vi(h));
        rep(i,h)
            rep(j,w){
                tmp[j][i] = grid[i][j];
            }
        grid = tmp;
    }
    swap(h,w);
    multiset<vi> rows;
    rep(i,h)
        rows.insert(grid[i]);
    while(sz(rows) >= 2){
        vi a = min(rows);
        rows.erase(rows.begin());
        vi b = a;
        reverse(all(b));
        auto it = rows.find(b);
        if(it != rows.end())
            rows.erase(it);
        else{
            if(a != b)
                return false;
        }
    }
    if(!rows.empty()){
        vi a = min(rows);
        vi b = a;
        reverse(all(b));
        if(a != b)
            return false;
    }
    return true;
}
bool solve(vvi grid){
    int n = sz(grid);
    int half = n/2;
    sort(all(grid));
    rep(bm,1<<n){
        if(__builtin_popcount(bm) != half) continue;
        vvi tmp;
        rep(i,n)
            if(bm&(1<<i))
                tmp.pb(grid[i]);
        rep(i,n)
            if(!(bm&(1<<i)))
                tmp.pb(grid[i]);
        do{
            if(check(tmp))
                return true;

        }while(next_permutation(tmp.begin()+half,tmp.end()));
    }
    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

Submission Time
Task E - Symmetric Grid
User Andres_Unt
Language C++ (GCC 9.2.1)
Score 700
Code Size 4621 Byte
Status AC
Exec Time 985 ms
Memory 3648 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 63
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 9 ms 3592 KB
10.txt AC 102 ms 3504 KB
100.txt AC 6 ms 3592 KB
11.txt AC 48 ms 3648 KB
12.txt AC 47 ms 3636 KB
13.txt AC 310 ms 3488 KB
14.txt AC 251 ms 3560 KB
15.txt AC 66 ms 3448 KB
16.txt AC 901 ms 3560 KB
17.txt AC 513 ms 3648 KB
18.txt AC 253 ms 3612 KB
19.txt AC 415 ms 3496 KB
2.txt AC 2 ms 3544 KB
20.txt AC 45 ms 3608 KB
21.txt AC 506 ms 3448 KB
22.txt AC 985 ms 3608 KB
23.txt AC 348 ms 3560 KB
24.txt AC 99 ms 3488 KB
25.txt AC 70 ms 3560 KB
26.txt AC 687 ms 3608 KB
27.txt AC 513 ms 3648 KB
28.txt AC 696 ms 3508 KB
29.txt AC 333 ms 3568 KB
3.txt AC 2 ms 3616 KB
30.txt AC 59 ms 3492 KB
31.txt AC 185 ms 3560 KB
32.txt AC 132 ms 3612 KB
33.txt AC 507 ms 3608 KB
34.txt AC 947 ms 3572 KB
35.txt AC 234 ms 3496 KB
36.txt AC 83 ms 3608 KB
37.txt AC 81 ms 3608 KB
38.txt AC 233 ms 3548 KB
39.txt AC 51 ms 3608 KB
4.txt AC 36 ms 3572 KB
40.txt AC 943 ms 3612 KB
41.txt AC 421 ms 3496 KB
42.txt AC 683 ms 3600 KB
43.txt AC 899 ms 3488 KB
44.txt AC 63 ms 3560 KB
45.txt AC 251 ms 3604 KB
46.txt AC 35 ms 3544 KB
47.txt AC 31 ms 3512 KB
48.txt AC 505 ms 3608 KB
49.txt AC 945 ms 3648 KB
5.txt AC 45 ms 3596 KB
50.txt AC 414 ms 3564 KB
51.txt AC 132 ms 3608 KB
52.txt AC 921 ms 3560 KB
53.txt AC 914 ms 3448 KB
54.txt AC 2 ms 3504 KB
55.txt AC 2 ms 3608 KB
56.txt AC 666 ms 3496 KB
6.txt AC 38 ms 3560 KB
7.txt AC 7 ms 3596 KB
8.txt AC 4 ms 3612 KB
9.txt AC 2 ms 3600 KB
sample1.txt AC 2 ms 3556 KB
sample2.txt AC 1 ms 3560 KB
sample3.txt AC 59 ms 3484 KB