fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int n,k;
  5. int pw(int a, int b, int mod){
  6. 	int ret = 1;
  7. 	while(b){
  8. 		if(b%2){
  9. 			ret = ret*a%mod;
  10. 		}
  11. 		a = a*a%mod;
  12. 		b>>=1;
  13. 	}
  14. 	return ret;
  15. }
  16. signed main() {
  17. 	cin>>n>>k;
  18. 	// cout<<pw(2,0,100);
  19. 	vector<int> nxt(n),p(n),pos(n);
  20. 	for(auto &i: p){
  21. 		 cin>>i;
  22. 		 i--;
  23. 	}
  24.  
  25. 	for(int i = 0;i<n;i++){
  26. 		nxt[i] = p[i];
  27. 		pos[p[i]] = i;
  28. 	}
  29. 	vector<int> ans(n);
  30. 	vector<bool> used(n,false);
  31. 	for(int i = 0;i<n;i++){
  32. 		vector<int> tmp;
  33. 		int node = i;
  34. 		while(!used[node]){
  35. 			used[node] = true;
  36. 			tmp.push_back(node);
  37. 			node = nxt[node];
  38. 		}
  39. 		if(tmp.size() == 0) continue;
  40. 		for(auto m: tmp) cout<<m<<" ";
  41. 		cout<<endl;
  42. 		int sz = tmp.size();
  43. 		int shift = pw(2LL,k,sz);
  44. 		for(int j = 0;j<tmp.size();j++){
  45. 			int position = pos[tmp[(j+shift)%(int)tmp.size()]];
  46. 			ans[position] = tmp[j];
  47. 		}
  48.  
  49. 	}
  50. 	for(int i = 0;i<n;i++){
  51. 		cout<<i+1<<": "<<ans[i]+1<<" "<<endl;
  52. 	}
  53. 	// for(auto i: ans) cout<<i+1<<" ";
  54.  
  55.  
  56. 	// your code goes here
  57. 	return 0;
  58. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
29 51912426
7 24 8 23 6 1 4 19 11 18 20 9 17 28 22 27 15 2 12 26 10 13 14 25 5 29 3 21 16
stdout
copy 
0 6 3 22 13 27 20 9 17 1 23 24 4 5 
2 7 18 11 8 10 19 25 28 15 26 
12 16 14 21 
1: 10 
2: 4 
3: 12 
4: 2 
5: 28 
6: 21 
7: 18 
8: 9 
9: 26 
10: 1 
11: 29 
12: 20 
13: 17 
14: 25 
15: 22 
16: 8 
17: 15 
18: 7 
19: 11 
20: 16 
21: 6 
22: 13 
23: 24 
24: 23 
25: 14 
26: 27 
27: 19 
28: 5 
29: 3
https://ideone.com/YZdJ6m
language:
C++14 (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!