fork download
copy 
  1. #include <iostream>
  2. #define MAXN 100005
  3. using namespace std;
  4. int N, A[MAXN], ans, Inversion[MAXN];
  5.  
  6. void swap(int i, int j)
  7. {
  8. 	int aux;
  9.  
  10. 	aux = A[Inversion[i]];
  11. 	A[Inversion[i]] = A[i];
  12. 	A[i] = aux;
  13. }
  14.  
  15. void calcularInversiones(int izq, int der)
  16. {
  17. 	/*if(izq == der)
  18. 		return;
  19.  
  20. 	int mid = (izq + der) / 2;
  21. 	calcularInversiones(izq, mid);
  22. 	calcularInversiones(mid + 1, der);
  23.  
  24. 	int indexIzq = izq;
  25. 	int indexDer = mid + 1;
  26. 	for(int i = izq; i <= der; i++)
  27. 	{
  28. 		if(indexIzq > mid) {
  29. 			mem[i] = a[indexDer++];
  30. 		}
  31. 		else if(indexDer > der);
  32. 		{
  33. 			mem[i] = a[indexIzq++];
  34. 		}
  35. 		else if(a[indexIzq] <= a[indexDer])
  36. 		{
  37. 			mem[i] = a[indexDer++];
  38. 		}
  39. 		else if(a[indexIzq] > a[indexDer])
  40. 		{
  41. 			mem[i] = a[indexIzq++];
  42. 		}
  43. 	}*/
  44.  
  45. 	int before = 0;
  46. 	for(int i = N; i >= 1; i--)
  47. 	{
  48. 		before = 0;
  49. 		for(int j = i + 1; j <= N; j++)
  50. 		{
  51. 			if(A[i] > A[j] && A[i] > A[Inversion[j]])
  52. 			{
  53. 				Inversion[before] = 0;
  54. 				//cout << A[i] << "-> " << A[j] << "\n";
  55. 				Inversion[i] = j;
  56. 				Inversion[j] = i;
  57. 				before = j;
  58. 			}
  59. 		}
  60. 	}
  61. }
  62.  
  63. int main()
  64. {
  65. 	cin >> N;
  66. 	for(int i = 1; i <= N; i++)
  67. 	{
  68. 		cin >> A[i];
  69. 	}
  70.  
  71. 	for(int j = 0; j < N; j++)
  72. 	{
  73. 		calcularInversiones(1, N);
  74. 		for(int i = 1; i <= N; i++)
  75. 		{
  76. 			//cout << i << ":" << Inversion[i] << "\n";
  77. 			if(Inversion[i] > 0 && i < Inversion[i])
  78. 			{
  79. 				ans++;
  80. 				swap(i, Inversion[i]);
  81. 			}
  82. 			Inversion[i] = 0;
  83. 		}
  84. 	}
  85.  
  86. 	cout << ans << "\n";
  87. 	for(int i = 1; i <= N; i++)
  88. 		cout << A[i] << " ";
  89. 	cout << "\n";
  90. 	return 0;
  91. }
  92.  
Success #stdin #stdout 0s 4292KB
comments (?)
stdin
copy 
4
2 5 3 1
stdout
copy 
2
1 2 3 5
https://ideone.com/W7myoc
language:
C++14 (gcc 8.3)
created:
6 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!