Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <iomanip>
- #include <string>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <map>
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
- #define all(a) a.begin(), a.end()
- #define mp make_pair
- #define pb(a) push_back(a)
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- //456, Задана перестановка p1, p2,..., pn (1 ≤ pi ≤ n).
- //Выведите ее квадратный корень, то есть такую перестановку q, что q^2=p, или No solution, если решения не существует.
- void cycleCount(const vector<int> &p)
- {
- vector<bool> used(p.size());
- vector<vector<int>> result;
- vector<vector<int>> place(p.size() + 1, vector<int>());
- map<int, int> sizes;
- vector<int> last(p.size() + 1, -1);
- int counter = -1;
- fore(i, 0, p.size())
- {
- if (!used[i])
- {
- ++counter;
- vector<int> v;
- int j = i;
- while(!used[j])
- {
- used[j] = true;
- v.push_back(j + 1);
- j = p[j] - 1;
- }
- v.push_back(v[0]);
- v.erase(v.begin());
- result.push_back(v);
- if(sizes[v.size()])
- sizes[v.size()]++;
- else
- sizes[v.size()] = 1;
- if(v.size() % 2 == 0)
- place[v.size()].push_back(counter);
- }
- }
- for(auto it = sizes.begin(); it != sizes.end(); ++it)
- {
- if(it->first % 2 == 0 && it->second % 2 == 1)
- {
- cout << "No solution\n";
- exit(0);
- }
- }
- for(int i = 0; i < place.size(); i++)//even-size cycles
- {
- while(!place[i].empty())
- {
- vector<int> v;
- set<int> s;
- for(int j = 0; j < i; j++)
- {
- v.push_back(result[place[i][0]][j]);
- s.insert(v.back());
- v.push_back(result[place[i][1]][j]);
- s.insert(v.back());
- }
- for(int j = 1; j < v.size(); j++)
- {
- last[v[j - 1]] = v[j];
- }
- last[v[v.size() - 1]] = v[0];
- place[i].erase(place[i].begin(), place[i].begin() + 2);
- }
- }
- //cout << "if you read this, it's too late\n";
- for(int i = 0; i < result.size(); i++)
- {
- int wow = result[i].size();
- if(wow % 2)
- {
- int cur = (wow + 1) / 2;
- for(int j = 0; j < wow; j++)
- {
- last[result[i][j]] = result[i][(j + cur) % wow];
- }
- }
- }
- for(int j = 1; j < last.size(); j++)
- cout << last[j] << " ";
- cout << endl;
- }
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n;
- cin >> n;
- vector<int> v(n);
- forn(i, n)
- {
- cin >> v[i];
- }
- cycleCount(v);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement