RpGFaC - Online C++ Compiler & Debugging Tool

/*
compute the positions (after all swaps) of largest numbers of even and odd parity
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		vector<int> a(n);
		for (int &x : a) cin >> x;

		vector<int> even, odd;
		for (int i = 0; i < n; i++) {
			if (i % 2 == 0) even.push_back(a[i]);
			else odd.push_back(a[i]);
		}


		sort(even.begin(), even.end());
		sort(odd.begin(), odd.end());

		int biggest_even = even.back();
		even.pop_back();
		int second_biggest_even = even.back();
		even.pop_back();

		int biggest_odd = odd.back();
		odd.pop_back();
		int second_biggest_odd = odd.back();
		odd.pop_back();

		int w = -1, x = -1, y = -1, z = -1;
		int e, f, g, h;
		for (int i = 0; i < n; i++) {
			if (a[i] == biggest_even) {
				if (w == -1) {
					e = i;
					w = a[i];
				} else {
					g = i;
					y = a[i];
				}
			}
			if (a[i] == second_biggest_even) {
				if (w == -1) {
					w = a[i];
					e = i;
				}
				else {
					y = a[i];
					g = i;
				}
			}
			if (a[i] == biggest_odd) {
				if (x == -1) {
					f = i;
					x = a[i];
				}
				else {
					h = i;
					z = a[i];
				}
			}
			if (a[i] == second_biggest_odd) {
				if (x == -1) {
					f = i;
					x = a[i];
				}
				else {
					h = i;
					z = a[i];
				}
			}
		}

		bool even_swap = true;
		for (int i = e + 1; i < g; i += 2) {
			cout << a[i] << " " << second_biggest_odd << " " << biggest_odd << '\n';
			if (a[i] == second_biggest_odd || a[i] == biggest_odd) even_swap = false;
		}
		bool odd_swap = true;
		for (int i = f + 1; i < h; i += 2) {
			if (a[i] == biggest_even || a[i] == second_biggest_even) odd_swap = false;
		}

		cout << even_swap << " " << odd_swap << '\n';

		if (even_swap) swap(w, y);
		if (odd_swap) swap(x, z);

		int offset = 0;
		for (int i = 0; i < n - 4; i++) {
			if (i % 2 == 0) {
				cout << even[i / 2] << ' ';
			} else {
				cout << odd[i / 2] << ' ';
			}
			offset++;
		}
		// w x y z or y z w x
		if (offset % 2 == 0) {
			if (w < y) {
				cout << w << ' ' << x << ' ' << y << ' ' << z << '\n';
			} else {
				cout << y << ' ' << z << ' ' << w << ' ' << x << '\n';
			}
		} else { // x w z y or z y x w
			if (x < z) {
				cout << x << ' ' << w << ' ' << z << ' ' << y << '\n';
			} else {
				cout << z << ' ' << y << ' ' << x << ' ' << w << '\n';
			}
		}
	}
}