結果

問題 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;	
}
0