fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define all(x) x.begin(), x.end()
  4. #define rall(x) x.rbegin(), x.rend()
  5. #define sz(x) (int)(x).size()
  6.  
  7. using namespace std;
  8. const double pi = acos(-1);
  9. const int mod = 1e9 + 7;
  10. const int N = 2e5 + 5, M = 1e2 + 2, K = 5e2 + 5;
  11.  
  12. int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
  13. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  14.  
  15. void fast()
  16. {
  17. #ifndef ONLINE_JUDGE
  18.     freopen("input.txt", "r", stdin);
  19.     freopen("output.txt", "w", stdout);
  20. #endif
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr), cout.tie(nullptr);
  23. }
  24.  
  25. deque<deque<int>> get_permutation_cycles(deque<int> perm)
  26. {
  27.     int n = perm.size();
  28.     deque<int> vis(n, 0);
  29.     deque<deque<int>> ans;
  30.  
  31.     for (int i = 0; i < n; i++)
  32.     {
  33.         if (vis[i])
  34.             continue;
  35.  
  36.         int d = perm[i];
  37.         deque<int> temp;
  38.         while (!vis[d])
  39.         {
  40.             temp.emplace_back(d);
  41.             vis[d] = 1, d = perm[d];
  42.         }
  43.  
  44.         ans.emplace_back(temp);
  45.     }
  46.     return ans;
  47. }
  48.  
  49. int32_t main()
  50. {
  51.     fast();
  52.  
  53.     int n;
  54.     cin >> n;
  55.     deque<int> p(n), p2(n), a(n);
  56.     for (auto &i : p)
  57.         cin >> i;
  58.     for (auto &i : a)
  59.         cin >> i;
  60.  
  61.     for (auto &i : a)
  62.         i--;
  63.     for (auto &i : p)
  64.         i--;
  65.  
  66.     deque<deque<int>> cycles = get_permutation_cycles(a), cycles2 = cycles, values_of_cycles;
  67.  
  68.     for (auto v : cycles)
  69.     {
  70.  
  71.         deque<int> d(v.size());
  72.  
  73.         for (int i = 0; i < v.size(); i++)
  74.             d[i] = p[v[i]];
  75.  
  76.         values_of_cycles.emplace_back(d);
  77.     }
  78.  
  79.     int i = 0;
  80.  
  81.     for (auto &v : values_of_cycles)
  82.     {
  83.         int min_ = *min_element(all(v));
  84.  
  85.         while (v.front() != min_)
  86.         {
  87.             int x = v.front(), y = cycles2[i].front();
  88.  
  89.             v.pop_front();
  90.             cycles2[i].pop_front();
  91.  
  92.             v.emplace_back(x);
  93.             cycles2.emplace_back(y);
  94.         }
  95.  
  96.         i++;
  97.     }
  98.  
  99.     i = 0;
  100.  
  101.     for (auto v : cycles2)
  102.     {
  103.         for (int j = 0; j < v.size(); j++)
  104.         {
  105.             int uu = 0;
  106.             p2[cycles[i][j]] = p[v[cycles2[i][j]]];
  107.         }
  108.         i++;
  109.     }
  110.  
  111.     for (auto &k : p2)
  112.         k++;
  113.     for (auto k : p2)
  114.         cout << k << " ";
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RgijR3
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!