Salvens

C

Jul 27th, 2023
966
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #include <array>
  2. #include <iostream>
  3. #include <vector>
  4. #include <map>
  5. #include <queue>
  6. #include <set>
  7. #include <stack>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12.  
  13. const long long INF = 1e18 + 7;
  14. const int MAXN = 2e5 + 10;
  15. const int N = 1e3;
  16.  
  17. int n;
  18. array<stack<int>, N> a;
  19. vector<pair<int, int>> ans;
  20.  
  21. void shift(int from, int to, int x) {
  22.     while (!a[from].empty() && a[from].top() == x) {
  23.         a[to].push(x);
  24.         a[from].pop();
  25.         ans.emplace_back(from + 1, to + 1);
  26.     }
  27. }
  28.  
  29. void shift_all(int from, int to) {
  30.     while (!a[from].empty()) {
  31.         a[to].push(a[from].top());
  32.         a[from].pop();
  33.         ans.emplace_back(from + 1, to + 1);
  34.     }
  35. }
  36.  
  37. void solve() {
  38.     while (!a[1].empty()) {
  39.         a[0].push(a[1].top());
  40.         a[1].pop();
  41.         ans.emplace_back(2, 1);
  42.     }
  43.     bool flag = false;
  44.     while (!a[0].empty()) {
  45.         if (a[0].top() == 0) {
  46.             flag = true;
  47.             a[0].pop();
  48.             a[1].push(0);
  49.         } else {
  50.             if (flag) {
  51.                 cout << 0 << '\n';
  52.                 exit(0);
  53.             }
  54.             a[0].pop();
  55.             a[1].push(1);
  56.         }
  57.         ans.emplace_back(1, 2);
  58.     }
  59.     shift(1, 0, 0);
  60.  
  61.     for (auto [x, y]: ans) {
  62.         cout << x << ' ' << y << '\n';
  63.     }
  64.     exit(0);
  65. }
  66.  
  67.  
  68. signed main() {
  69.     ios_base::sync_with_stdio(false);
  70.     cin.tie(nullptr);
  71.     cout.tie(nullptr);
  72.     cin >> n;
  73.     bool flag = true;
  74.     for (int i = 0; i < n; ++i) {
  75.         int k;
  76.         cin >> k;
  77.         for (int j = 0; j < k; ++j) {
  78.             int x;
  79.             cin >> x;
  80.             --x;
  81.             a[i].push(x);
  82.             if (x != i) {
  83.                 flag = false;
  84.             }
  85.         }
  86.     }
  87.  
  88.     if (flag) {
  89.         return 0;
  90.     }
  91.     if (n == 2) {
  92.         solve();
  93.     }
  94.     for (int i = 1; i < n; ++i) {
  95.         shift_all(i, 0);
  96.     }
  97.     while (!a[0].empty()) {
  98.         if (a[0].top() == 2) {
  99.             a[2].push(a[0].top());
  100.             ans.emplace_back(1, 3);
  101.         } else {
  102.             a[1].push(a[0].top());
  103.             ans.emplace_back(1, 2);
  104.         }
  105.         a[0].pop();
  106.     }
  107.     while (!a[1].empty()) {
  108.         if (a[1].top() == 1) {
  109.             a[2].push(a[1].top());
  110.             a[1].pop();
  111.             ans.emplace_back(2, 3);
  112.         } else {
  113.             int pos = a[1].top();
  114.             a[pos].push(a[1].top());
  115.             a[1].pop();
  116.             ans.emplace_back(2, pos + 1);
  117.         }
  118.     }
  119.     shift(2, 1, 1);
  120.  
  121.     for (auto [x, y]: ans) {
  122.         cout << x << ' ' << y << '\n';
  123.     }
  124. }
  125.  
Advertisement
Add Comment
Please, Sign In to add comment