提出 #48394120

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>

namespace {
    using ModInt [[maybe_unused]] = atcoder::modint998244353;
    using Num [[maybe_unused]] = long long int;
    using Vec [[maybe_unused]] = std::vector<Num>;
    using Set [[maybe_unused]] = std::set<Num>;
    using Mset [[maybe_unused]] = std::multiset<Num>;
    using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

    template<typename T>
    using Q [[maybe_unused]] = std::queue<T>;

    template<typename T>
    using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

Num ga[8][8];
Num gb[8][8];

void solve(std::istream& is, std::ostream& os) {
    Num h, w;
    is >> h >> w;

    std::map<Num, Num> ma;
    for(Num y{0}; y<h; ++y) {
        for(Num x{0}; x<w; ++x) {
            Num a;
            is >> a;
            ga[y][x] = a;
            ma[a] += 1;
        }
    }

    std::map<Num, Num> mb;
    for(Num y{0}; y<h; ++y) {
        for(Num x{0}; x<w; ++x) {
            Num b;
            is >> b;
            gb[y][x] = b;
            mb[b] += 1;
        }
    }

    for(const auto& [k,v] : ma) {
        if (mb[k] != v) {
            os << "-1\n";
            return;
        }
    }

    for(const auto& [k,v] : mb) {
        if (ma[k] != v) {
            os << "-1\n";
            return;
        }
    }

    Vec perm_y(h);
    std::iota(perm_y.begin(), perm_y.end(), 0LL);

    constexpr Num Inf = 1000000000000LL;
    Num answer {Inf};
    do {
        Vec perm_x(w);
        std::iota(perm_x.begin(), perm_x.end(), 0LL);
        do {
            bool matched {true};
            for(Num from_y{0}; from_y<h; ++from_y) {
                const auto to_y = perm_y.at(from_y);
                for(Num from_x{0}; from_x<w; ++from_x) {
                    const auto to_x = perm_x.at(from_x);
                    matched &= (ga[to_y][to_x] == gb[from_y][from_x]);
                }
            }

            if (matched) {
                Num cty {0};
                for(Num i{0}; i<h; ++i) {
                    for(Num j{i+1}; j<h; ++j) {
                        cty += perm_y.at(i) > perm_y.at(j);
                    }
                }

                Num ctx {0};
                for(Num i{0}; i<w; ++i) {
                    for(Num j{i+1}; j<w; ++j) {
                        ctx += perm_x.at(i) > perm_x.at(j);
                    }
                }

                answer = std::min(answer, ctx + cty);
            }
        } while(std::next_permutation(perm_x.begin(), perm_x.end()));
    } while(std::next_permutation(perm_y.begin(), perm_y.end()));

    answer = (answer == Inf) ? -1 : answer;
    os << answer << "\n";
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

提出情報

ジャッジ結果