fork download
copy 
  1. /* 
  2. compute the positions (after all swaps) of largest numbers of even and odd parity
  3. */
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <algorithm>
  8. using namespace std;
  9.  
  10. int main() {
  11. 	cin.tie(0)->sync_with_stdio(0);
  12. 	int t; cin >> t;
  13. 	while (t--) {
  14. 		int n; cin >> n;
  15. 		vector<int> a(n);
  16. 		for (int &x : a) cin >> x;
  17.  
  18. 		vector<int> even, odd;
  19. 		for (int i = 0; i < n; i++) {
  20. 			if (i % 2 == 0) even.push_back(a[i]);
  21. 			else odd.push_back(a[i]);
  22. 		}
  23.  
  24.  
  25. 		sort(even.begin(), even.end());
  26. 		sort(odd.begin(), odd.end());
  27.  
  28. 		int biggest_even = even.back();
  29. 		even.pop_back();
  30. 		int second_biggest_even = even.back();
  31. 		even.pop_back();
  32.  
  33. 		int biggest_odd = odd.back();
  34. 		odd.pop_back();
  35. 		int second_biggest_odd = odd.back();
  36. 		odd.pop_back();
  37.  
  38. 		int w = -1, x = -1, y = -1, z = -1;
  39. 		int e, f, g, h;
  40. 		for (int i = 0; i < n; i++) {
  41. 			if (a[i] == biggest_even) {
  42. 				if (w == -1) {
  43. 					e = i;
  44. 					w = a[i];
  45. 				} else {
  46. 					g = i;
  47. 					y = a[i];
  48. 				}
  49. 			} 
  50. 			if (a[i] == second_biggest_even) {
  51. 				if (w == -1) {
  52. 					w = a[i];
  53. 					e = i;
  54. 				}
  55. 				else {
  56. 					y = a[i];
  57. 					g = i;
  58. 				}
  59. 			}
  60. 			if (a[i] == biggest_odd) {
  61. 				if (x == -1) {
  62. 					f = i;
  63. 					x = a[i];
  64. 				}
  65. 				else {
  66. 					h = i;
  67. 					z = a[i];
  68. 				}
  69. 			} 
  70. 			if (a[i] == second_biggest_odd) {
  71. 				if (x == -1) {
  72. 					f = i;
  73. 					x = a[i];
  74. 				}
  75. 				else {
  76. 					h = i;
  77. 					z = a[i];
  78. 				}
  79. 			}
  80. 		}
  81.  
  82. 		bool even_swap = true;
  83. 		for (int i = e + 1; i < g; i += 2) {
  84. 			cout << a[i] << " " << second_biggest_odd << " " << biggest_odd << '\n';
  85. 			if (a[i] == second_biggest_odd || a[i] == biggest_odd) even_swap = false;
  86. 		}
  87. 		bool odd_swap = true;
  88. 		for (int i = f + 1; i < h; i += 2) {
  89. 			if (a[i] == biggest_even || a[i] == second_biggest_even) odd_swap = false;
  90. 		}
  91.  
  92. 		cout << even_swap << " " << odd_swap << '\n';
  93.  
  94. 		if (even_swap) swap(w, y);
  95. 		if (odd_swap) swap(x, z);
  96.  
  97. 		int offset = 0;
  98. 		for (int i = 0; i < n - 4; i++) {
  99. 			if (i % 2 == 0) {
  100. 				cout << even[i / 2] << ' ';
  101. 			} else {
  102. 				cout << odd[i / 2] << ' ';
  103. 			}
  104. 			offset++;
  105. 		} 
  106. 		// w x y z or y z w x
  107. 		if (offset % 2 == 0) {
  108. 			if (w < y) {
  109. 				cout << w << ' ' << x << ' ' << y << ' ' << z << '\n';
  110. 			} else {
  111. 				cout << y << ' ' << z << ' ' << w << ' ' << x << '\n';
  112. 			}
  113. 		} else { // x w z y or z y x w
  114. 			if (x < z) {
  115. 				cout << x << ' ' << w << ' ' << z << ' ' << y << '\n';
  116. 			} else {
  117. 				cout << z << ' ' << y << ' ' << x << ' ' << w << '\n';
  118. 			}
  119. 		}
  120. 	}
  121. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
1
4
2 1 3 4
stdout
copy 
1 1 4
0 0
2 1 3 4
https://ideone.com/RpGFaC
language:
C++ (gcc 8.3)
created:
4 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!