Advertisement
Guest User

Untitled

a guest
Mar 13th, 2021
668
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5.  
  6. using namespace std;
  7. using vi = vector<int>;
  8.  
  9. bool isSame(vector<vi> a, vector<vi> b) {
  10.     sort(a.begin(), a.end());
  11.     sort(b.begin(), b.end());
  12.     return a == b;
  13. }
  14.  
  15. int main() {
  16.     ios::sync_with_stdio(0); cin.tie(0);
  17.  
  18.     int n, m; cin >> n >> m;
  19.     vector a(n, vi(m)); for (auto& v : a) for (int& x : v) cin >> x;
  20.     vector b(n, vi(m)); for (auto& v : b) for (int& x : v) cin >> x;
  21.     vector<int> inv(m), act;
  22.  
  23.     for (int i = 0; i < m; ++i) {
  24.         for (int j = 1; j < n; ++j) {
  25.             if (b[j][i] < b[j - 1][i]) ++inv[i];
  26.         }
  27.     }
  28.  
  29.     int ans = -1;
  30.  
  31.     vector<int> cut(n - 1);
  32.     queue<int> q;
  33.  
  34.     for (int i = 0; i < m; ++i) if (!inv[i]) q.push(i);
  35.  
  36.     while (!q.empty()) {
  37.         int v = q.front(); q.pop();
  38.         act.push_back(v);
  39.  
  40.         for (int i = 1; i < n; ++i) {
  41.             if (b[i][v] > b[i - 1][v] && !cut[i - 1]) {
  42.                 cut[i - 1] = 1;
  43.                 for (int j = 0; j < m; ++j) {
  44.                     if (b[i][j] < b[i - 1][j]) {
  45.                         --inv[j];
  46.                         if (inv[j] == 0) {
  47.                             q.push(j);
  48.                         }
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.     }
  54.  
  55.     reverse(act.begin(), act.end());
  56.     for (int j : act) {
  57.         stable_sort(a.begin(), a.end(), [&](auto& l, auto& r) {
  58.             return l[j] < r[j];
  59.             });
  60.     }
  61.  
  62.     if (a == b) ans = act.size();
  63.  
  64.     cout << ans << endl;
  65.     if (ans != -1) {
  66.         for (int i : act) cout << i + 1 << ' ';
  67.         cout << endl;
  68.     }
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement