Submission #19305527


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 F - Permutation Tree
User Andres_Unt
Language C++ (GCC 9.2.1)
Score 0
Code Size 4621 Byte
Status RE
Exec Time 2353 ms
Memory 3457768 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
WA × 2
TLE × 1
WA × 30
TLE × 11
RE × 14
Set Name Test Cases
Sample sample1.txt, sampleId.txt, sampleNo.txt
All id.txt, oshii_0.txt, oshii_1.txt, rnd10000_9876.txt, rnd10_4.txt, rnd10_l.txt, rnd20000_9876.txt, rnd20_18.txt, rnd20_4.txt, rnd20_l.txt, rnd3000_2984.txt, rnd3000_l.txt, rnd_0.txt, rnd_1.txt, rnd_10.txt, rnd_100.txt, rnd_1000.txt, rnd_10000.txt, rnd_100000.txt, rnd_1000000.txt, rnd_1000001.txt, rnd_1000002.txt, rnd_100001.txt, rnd_100002.txt, rnd_10001.txt, rnd_10002.txt, rnd_1001.txt, rnd_1002.txt, rnd_101.txt, rnd_102.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, rnd_5.txt, rnd_6.txt, rnd_7.txt, rnd_70.txt, rnd_700.txt, rnd_7000.txt, rnd_70000.txt, rnd_700000.txt, rnd_700001.txt, rnd_700002.txt, rnd_70001.txt, rnd_70002.txt, rnd_7001.txt, rnd_7002.txt, rnd_701.txt, rnd_702.txt, rnd_71.txt, rnd_72.txt, sample1.txt, sampleId.txt, sampleNo.txt, star.txt
Case Name Status Exec Time Memory
id.txt TLE 2267 ms 3455212 KB
oshii_0.txt RE 1984 ms 3455232 KB
oshii_1.txt RE 1976 ms 3455876 KB
rnd10000_9876.txt WA 293 ms 107696 KB
rnd10_4.txt WA 25 ms 3468 KB
rnd10_l.txt WA 14 ms 3544 KB
rnd20000_9876.txt TLE 2248 ms 1393376 KB
rnd20_18.txt TLE 2205 ms 3292 KB
rnd20_4.txt TLE 2205 ms 3292 KB
rnd20_l.txt TLE 2205 ms 3284 KB
rnd3000_2984.txt WA 125 ms 31560 KB
rnd3000_l.txt WA 70 ms 3924 KB
rnd_0.txt RE 2154 ms 3456652 KB
rnd_1.txt TLE 2270 ms 2274608 KB
rnd_10.txt WA 22 ms 3448 KB
rnd_100.txt WA 2 ms 3492 KB
rnd_1000.txt WA 24 ms 9780 KB
rnd_10000.txt WA 421 ms 183840 KB
rnd_100000.txt RE 2134 ms 3457768 KB
rnd_1000000.txt RE 2021 ms 3456820 KB
rnd_1000001.txt RE 2026 ms 3456008 KB
rnd_1000002.txt RE 2162 ms 3456960 KB
rnd_100001.txt WA 103 ms 39352 KB
rnd_100002.txt WA 170 ms 72328 KB
rnd_10001.txt WA 21 ms 8756 KB
rnd_10002.txt WA 13 ms 6060 KB
rnd_1001.txt WA 2 ms 3476 KB
rnd_1002.txt WA 2 ms 3604 KB
rnd_101.txt WA 13 ms 3476 KB
rnd_102.txt WA 13 ms 3588 KB
rnd_2.txt RE 2104 ms 3453576 KB
rnd_3.txt TLE 2288 ms 2999292 KB
rnd_4.txt RE 2057 ms 3455876 KB
rnd_5.txt RE 2190 ms 3456204 KB
rnd_6.txt RE 2136 ms 3456276 KB
rnd_7.txt TLE 2215 ms 3454668 KB
rnd_70.txt WA 31 ms 5220 KB
rnd_700.txt WA 887 ms 3604 KB
rnd_7000.txt WA 306 ms 113524 KB
rnd_70000.txt TLE 2353 ms 3455184 KB
rnd_700000.txt RE 2158 ms 3456416 KB
rnd_700001.txt RE 2165 ms 3456528 KB
rnd_700002.txt TLE 2350 ms 3455752 KB
rnd_70001.txt WA 147 ms 28352 KB
rnd_70002.txt WA 131 ms 32824 KB
rnd_7001.txt WA 888 ms 3988 KB
rnd_7002.txt WA 886 ms 4240 KB
rnd_701.txt WA 2 ms 3604 KB
rnd_702.txt WA 2 ms 3464 KB
rnd_71.txt WA 2 ms 3424 KB
rnd_72.txt WA 2 ms 3572 KB
sample1.txt WA 2 ms 3416 KB
sampleId.txt WA 4 ms 3544 KB
sampleNo.txt TLE 2205 ms 3192 KB
star.txt RE 2100 ms 3456480 KB