結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-11-29 12:53:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 204 ms / 2,000 ms
コード長 3,341 bytes
コンパイル時間 1,501 ms
コンパイル使用メモリ 92,620 KB
実行使用メモリ 132,480 KB
最終ジャッジ日時 2024-12-02 12:32:00
合計ジャッジ時間 5,786 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// yukicoder - ProblemID 11672 - writer's solution
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using std::vector;
class PPuzzle {
    vector<vector<int>> f;
public:
    const int n;
    PPuzzle(int n) : n(n) {}
    PPuzzle* scan() {
        this->f.resize(this->n);
        std::for_each(this->f.begin(), this->f.end(), 
            [this](auto &row) {
                row.resize(this->n); 
                std::for_each(row.begin(), row.end(), 
                    [](auto &i) { std::cin >> i; });
            });
        return this;
    }
    PPuzzle* clone() const {
        auto p = new PPuzzle(this->n);
        p->f = this->f;
        return p;
    }
    const vector<int> select_col(int c) const {
        vector<int> s(this->n);
        std::transform(this->f.begin(), this->f.end(), s.begin(),
            [c](auto &row) { return row[c-1]; });
        return s;
    }
    const vector<int> select_row(int r) const {
        return this->f[r-1];
    }
    void operate_col(int c) {
        auto s = this->select_col(c);
        vector<vector<int>> tmp(this->n);
        for (auto rf=this->f.begin(), rt=tmp.begin(); rt!=tmp.end(); rf++,rt++) {
            rt->resize(this->n);
            for (int i=0; i<this->n; i++) {
                rt->at(s[i]-1) = rf->at(i);
            }
        }
        this->f.swap(tmp);
    }
    void operate_row(int r) {
        auto s = this->select_row(r);
        vector<vector<int>> tmp(this->n);
        for (int i=0; i<this->n; i++) {
            tmp[s[i]-1].swap(this->f[i]);
        }
        this->f.swap(tmp);
    }
    bool is_same(const PPuzzle *other) const {
        return this->f == other->f;
    }
};
class Problem {
    Problem(int n, int k, PPuzzle *a, PPuzzle *b) : N(n), K(k), A(a), B(b) {}
public:
    const int N, K;
    const PPuzzle *A, *B;
    static const Problem* scan() {
        int n, k;
        std::cin >> n >> k;
        auto a = (new PPuzzle(n))->scan();
        auto b = (new PPuzzle(n))->scan();
        return new Problem(n, k, a, b);
    }
};
bool search(const Problem *p, int k, const PPuzzle *x, vector<int> &m) {
    if (k == 0) {
        return p->B->is_same(x);
    }
    for (int i=1; i<=p->N*2; i++) {
        auto y = x->clone();
        m.push_back(i);
        if (i <= p->N) {
            y->operate_col(i);
        } else {
            y->operate_row(i-p->N);
        }
        if (search(p, k-1, y, m)) {
            return true;
        }
        m.pop_back();
    }
    return false;
}
int cycle(vector<int> &v) {
    vector<int> t(v.size()), w(v);
    for (int cnt=1; ; cnt++) {
        for (int i=0; i<v.size(); i++) {
            t[v[i]-1] = w[i];
        }
        w.swap(t);
        if (w==v) {
            return cnt;
        }
    }
}
vector<int> solve(const Problem *p) {
    
    vector<int> m;
    search(p, p->K, p->A, m);
    
    vector<std::tuple<int,vector<int>>> v;
    auto a = p->A->clone();
    std::for_each(m.begin(), m.end(),
        [&v,&a](int i) {
            auto s = i <= a->n
                   ? a->select_col(i)
                   : a->select_row(i-a->n);
            v.push_back(std::make_tuple(i, s));
            if (i <= a->n) {
                a->operate_col(i);
            } else {
                a->operate_row(i-a->n);
            }
        });
    
    vector<int> ans;
    std::for_each(v.rbegin(), v.rend(),
        [&p,&ans](auto tp) {
            auto i = std::get<0>(tp);
            auto &s = std::get<1>(tp);
            auto h = i <= p->N ? i : (i-p->N);
            for (int cnt=cycle(s)-1; cnt>0; cnt--) {
                h = s[h-1];
                ans.push_back(i <= p->N ? h : (h+p->N));
            }
        });
    return ans;
}
int main() {
    auto p = Problem::scan();
    
    auto ans = solve(p);
    std::cout << ans.size() << '\n';
    std::for_each(ans.begin(), ans.end(),
        [p](int i) { 
            if (i <= p->N) {
                std::cout << "C " << i << '\n';
            } else {
                std::cout << "R " << (i-p->N) << '\n';
            }
        });
    return 0;   
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0