Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <array>
- #include <iostream>
- #include <vector>
- #include <map>
- #include <queue>
- #include <set>
- #include <stack>
- using namespace std;
- #define int long long
- const long long INF = 1e18 + 7;
- const int MAXN = 2e5 + 10;
- const int N = 1e3;
- int n;
- array<stack<int>, N> a;
- vector<pair<int, int>> ans;
- void shift(int from, int to, int x) {
- while (!a[from].empty() && a[from].top() == x) {
- a[to].push(x);
- a[from].pop();
- ans.emplace_back(from + 1, to + 1);
- }
- }
- void shift_all(int from, int to) {
- while (!a[from].empty()) {
- a[to].push(a[from].top());
- a[from].pop();
- ans.emplace_back(from + 1, to + 1);
- }
- }
- void solve() {
- while (!a[1].empty()) {
- a[0].push(a[1].top());
- a[1].pop();
- ans.emplace_back(2, 1);
- }
- bool flag = false;
- while (!a[0].empty()) {
- if (a[0].top() == 0) {
- flag = true;
- a[0].pop();
- a[1].push(0);
- } else {
- if (flag) {
- cout << 0 << '\n';
- exit(0);
- }
- a[0].pop();
- a[1].push(1);
- }
- ans.emplace_back(1, 2);
- }
- shift(1, 0, 0);
- for (auto [x, y]: ans) {
- cout << x << ' ' << y << '\n';
- }
- exit(0);
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cin >> n;
- bool flag = true;
- for (int i = 0; i < n; ++i) {
- int k;
- cin >> k;
- for (int j = 0; j < k; ++j) {
- int x;
- cin >> x;
- --x;
- a[i].push(x);
- if (x != i) {
- flag = false;
- }
- }
- }
- if (flag) {
- return 0;
- }
- if (n == 2) {
- solve();
- }
- for (int i = 1; i < n; ++i) {
- shift_all(i, 0);
- }
- while (!a[0].empty()) {
- if (a[0].top() == 2) {
- a[2].push(a[0].top());
- ans.emplace_back(1, 3);
- } else {
- a[1].push(a[0].top());
- ans.emplace_back(1, 2);
- }
- a[0].pop();
- }
- while (!a[1].empty()) {
- if (a[1].top() == 1) {
- a[2].push(a[1].top());
- a[1].pop();
- ans.emplace_back(2, 3);
- } else {
- int pos = a[1].top();
- a[pos].push(a[1].top());
- a[1].pop();
- ans.emplace_back(2, pos + 1);
- }
- }
- shift(2, 1, 1);
- for (auto [x, y]: ans) {
- cout << x << ' ' << y << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment