Advertisement
kokokozhina

456

Mar 6th, 2016
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.60 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. //456, Задана перестановка p1, p2,..., pn (1 ≤ pi ≤ n).
  23. //Выведите ее квадратный корень, то есть такую перестановку q, что q^2=p, или No solution, если решения не существует.
  24.  
  25. void cycleCount(const vector<int> &p)
  26. {
  27.     vector<bool> used(p.size());
  28.     vector<vector<int>> result;
  29.     vector<vector<int>> place(p.size() + 1, vector<int>());
  30.     map<int, int> sizes;
  31.     vector<int> last(p.size() + 1, -1);
  32.     int counter = -1;
  33.     fore(i, 0, p.size())
  34.     {
  35.         if (!used[i])
  36.         {
  37.             ++counter;
  38.             vector<int> v;
  39.             int j = i;
  40.             while(!used[j])
  41.             {
  42.                 used[j] = true;
  43.                 v.push_back(j + 1);
  44.                 j = p[j] - 1;
  45.             }
  46.             v.push_back(v[0]);
  47.             v.erase(v.begin());
  48.             result.push_back(v);
  49.             if(sizes[v.size()])
  50.                 sizes[v.size()]++;
  51.             else
  52.                 sizes[v.size()] = 1;
  53.             if(v.size() % 2 == 0)
  54.                 place[v.size()].push_back(counter);
  55.         }
  56.     }
  57.     for(auto it = sizes.begin(); it != sizes.end(); ++it)
  58.     {
  59.         if(it->first % 2 == 0 && it->second % 2 == 1)
  60.         {
  61.             cout << "No solution\n";
  62.             exit(0);
  63.         }
  64.     }
  65.     for(int i = 0; i < place.size(); i++)//even-size cycles
  66.     {
  67.         while(!place[i].empty())
  68.         {
  69.             vector<int> v;
  70.             set<int> s;
  71.             for(int j = 0; j < i; j++)
  72.             {
  73.                 v.push_back(result[place[i][0]][j]);
  74.                 s.insert(v.back());
  75.                 v.push_back(result[place[i][1]][j]);
  76.                 s.insert(v.back());
  77.             }
  78.            
  79.             for(int j = 1; j < v.size(); j++)
  80.             {
  81.                 last[v[j - 1]] = v[j];
  82.             }
  83.             last[v[v.size() - 1]] = v[0];          
  84.             place[i].erase(place[i].begin(), place[i].begin() + 2);
  85.         }
  86.     }
  87.     //cout << "if you read this, it's too late\n";
  88.    
  89.     for(int i = 0; i < result.size(); i++)
  90.     {
  91.         int wow = result[i].size();
  92.         if(wow % 2)
  93.         {
  94.             int cur = (wow + 1) / 2;
  95.             for(int j = 0; j < wow; j++)
  96.             {
  97.                 last[result[i][j]] = result[i][(j + cur) % wow];
  98.             }
  99.         }
  100.     }
  101.     for(int j = 1; j < last.size(); j++)
  102.         cout << last[j] << " ";
  103.     cout << endl;
  104. }
  105.  
  106. int main()
  107. {
  108. #ifdef _DEBUG
  109.     freopen("input.txt", "r", stdin);
  110.     freopen("output.txt", "w", stdout);
  111. #endif
  112.  
  113.     int n;
  114.     cin >> n;
  115.     vector<int> v(n);
  116.     forn(i, n)
  117.     {
  118.         cin >> v[i];
  119.     }
  120.     cycleCount(v);
  121.     return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement