Advertisement
kokokozhina

Untitled

Mar 3rd, 2016
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <string>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10.  
  11. #define forn(i, n) for (int i = 0; i < int(n); i++)
  12. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  13. #define all(a) a.begin(), a.end()
  14. #define mp make_pair
  15. #define pb(a) push_back(a)
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef pair<int, int> pii;
  21.  
  22. //484, Возведите заданную перестановку p в степень k.
  23.  
  24. void takeDegree(int m, vector<int> &p, int n)
  25. {
  26.     vector<bool> used(p.size());
  27.     vector<vector<int*>> result;
  28.     vector<map<int, int*>> rsrv;
  29.     int counter = -1;
  30.     fore(i, 0, p.size())
  31.     {
  32.         if (!used[i])
  33.         {
  34.             counter++;
  35.             vector<int*> worker;
  36.             map<int, int*> needed;
  37.             int j = i;
  38.             while(!used[j])
  39.             {
  40.                 used[j] = true;
  41.                 worker.push_back(&p[j]);
  42.                 needed[j] = &p[j];
  43.                 j = p[j];
  44.             }
  45.             result.push_back(worker);
  46.             rsrv.push_back(needed);
  47.         }
  48.     }
  49.  
  50.     vector<int> worker(n, -1);
  51.     fore(i, 0, result.size())
  52.     {
  53.         if(m % result[i].size() != 1)
  54.         {
  55.             fore(z, 0, result[i].size())
  56.             {
  57.                 worker[*result[i][(z + m % result[i].size()) % result[i].size()]] = *result[i][z];
  58.             }
  59.         }
  60.         else
  61.         {
  62.             for(auto it = rsrv[i].begin(); it != rsrv[i].end(); ++it)
  63.             {
  64.                 worker[it->first] = *it->second;
  65.             }
  66.         }
  67.  
  68.     }
  69.     fore(i, 0, n)
  70.         printf("%d ", worker[i]);
  71.  
  72. }
  73.  
  74.  
  75. int main()
  76. {
  77. #ifdef _DEBUG
  78.     freopen("input.txt", "r", stdin);
  79.     freopen("output.txt", "w", stdout);
  80. #endif
  81.  
  82.     int n, k;
  83.     scanf("%d%d", &n, &k);
  84.     vector<int> v(n);
  85.     forn(i, n)
  86.     {
  87.         int cur;
  88.         scanf("%d", &cur);
  89.         v[i] = cur;
  90.     }
  91.     takeDegree(k, v, n);
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement