fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define debug cout<<"masuk\n";
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. 	int n,k;
  8. 	scanf("%d",&n);
  9. 	int a[n];
  10. 	int temp,temp2,temp3;
  11. 	for(temp=0;temp<n;temp++)
  12. 	{
  13. 		scanf("%d",&a[temp]);
  14. 	}
  15. 	scanf("%d",&k);
  16. 	vector<vector<int>> adj(n);
  17. 	for(temp=0;temp<n;temp++)
  18. 	{
  19. 		int cnt=1;
  20. 		for(temp2=0;temp2<n;temp2++)
  21. 		{
  22. 			if((temp2>=temp)&&(temp2<temp+k)&&(temp+k-cnt<n))
  23. 			{
  24. 				adj[temp2].push_back(temp+k-cnt);
  25. 				cnt++;
  26. 			}
  27. 			else
  28. 			{
  29. 				adj[temp2].push_back(temp2);
  30. 			}
  31. 		}
  32. 	}
  33. 	/*for(temp=0;temp<n;temp++)
  34. 	{
  35. 		printf("%d contains : ",temp);
  36. 		for(temp2=0;temp2<adj[temp].size();temp2++)
  37. 		{
  38. 			cout<<adj[temp][temp2]<<" ";
  39. 		}
  40. 		cout<<"\n";
  41. 	}*/
  42. 	int cnt=0;
  43. 	for(temp=0;temp<n;temp++)
  44. 	{
  45. 		int  source[n];
  46. 		bool visited[n];
  47. 		for(temp2=temp;temp2<n;temp2++)
  48. 		{
  49. 			if(a[temp2]==temp+1)	break;
  50.  
  51. 		}
  52. 		if(temp2==temp)
  53. 		{
  54. 			continue;
  55. 		}
  56. 		int start=temp2;
  57. 		for(temp2=0;temp2<n;temp2++)
  58. 		{
  59. 			source[temp2]=-1;
  60. 			visited[temp2]=false;
  61. 		}
  62. 		int pos=start;
  63. 		queue<int> q;
  64. 		q.push(pos);
  65. 		while(!q.empty())
  66. 		{
  67.  
  68. 			pos=q.front();
  69. 			q.pop();
  70. 			visited[pos]=true;
  71. 			if(pos==temp)	break;
  72. 			for(temp2=0;temp2<adj[pos].size();temp2++)
  73. 			{
  74. 				int thenode=adj[pos][temp2];
  75. 				bool cokor=true;
  76. 				for(int tmp=temp;tmp<n;tmp++)
  77. 				{
  78. 					int check=adj[tmp][temp2];
  79. 					if(check<temp)	cokor=false;
  80. 				}
  81. 				if((!visited[thenode])&&(cokor))
  82. 				{
  83. 					source[thenode]=pos;
  84. 					q.push(thenode);
  85. 				}
  86. 			}
  87. 		}
  88. 		if(source[temp]==-1)
  89. 		{
  90. 			cout<<-1<<"\n";
  91. 			return 0;
  92. 		}
  93. 		vector<int> ans;
  94. 		pos=temp;
  95. 		while(source[pos]!=-1)
  96. 		{
  97. 			ans.push_back(pos);
  98. 			pos=source[pos];
  99.  
  100. 		}
  101. 		pos=start;
  102. 		cnt+=ans.size();
  103. 		for(temp2=ans.size()-1;temp2>=0;temp2--)
  104. 		{
  105. 			for(temp3=0;temp3<adj[pos].size();temp3++)
  106. 			{
  107. 				int thenode=adj[pos][temp3];
  108. 				if(thenode==ans[temp2])
  109. 				{
  110. 					break;
  111. 				}
  112. 			}
  113. 			int kursor=temp3;
  114. 			int b[n];
  115. 			for(temp3=0;temp3<n;temp3++)	b[temp3]=a[temp3];
  116. 			for(temp3=0;temp3<n;temp3++)
  117. 			{
  118. 				a[temp3]=b[adj[temp3][kursor]];
  119. 			}
  120. 			pos=ans[temp2];
  121. 		}
  122. 		//for(temp3=0;temp3<n;temp3++)	cout<<a[temp3]<<" "; cout<<"\n";
  123. 	}
  124. 	cout<<cnt<<"\n";
  125. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
5
5 4 1 2 3
3
stdout
copy 
3
https://ideone.com/3x2vwP
language:
C++14 (gcc 8.3)
created:
8 years 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!