Järjestäminen

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int N = 1 << 7;
int p[2*N];
 
int sum(int a, int b) {
	a += N;
	b += N;
	int s = 0;
	while (a <= b) {
		if (a % 2 == 1) s += p[a++];
		if (b % 2 == 0) s += p[b--];
		a /= 2;
		b /= 2;
	}
	return s;
}
 
void add(int k) {
	k += N;
	++p[k];
	for (k /= 2; k >= 1; k /= 2) {
		p[k] = p[2 * k] + p[2 * k + 1];
	}
}
 
int getinv(vector<int>& v) {
	int n = v.size();
	for (int i = 0; i < 2*N; ++i) p[i] = 0;
 
	int s = 0;
	for (int i = 0; i < n; ++i) {
		int x = v[i];
		s += sum(x + 1, N - 1);
		add(x);
	}
	return s;
}
 
int inv(vector<int>& v, int a, int b) {
	int p = 0;
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			if (v[a - i] > v[b - j]) ++p;
			if (v[a - i] < v[b - j]) --p;
		}
	}
	return p;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	int t;
	cin >> t;
 
	while (t--) {
		int n;
		cin >> n;
 
		vector<int> v(n);
		for (int i = 0; i < n; ++i) cin >> v[i];
 
		int s = getinv(v);
		if (s % 2 != 0 || s == 2) {
			cout << "NO\n";
			continue;
		}
 
		int amt = 0;
		while (s > 0) {
			++amt;
			if (amt > n*n) break;
 
			for (int a = 1; a < n; ++a) {
				for (int b = a+2; b < n; ++b) {
					int r = inv(v, a, b);
					if (inv(v, a, b) >= 0) {
						if (s == 4 && r == 2) continue;
						s -= r;
						swap(v[a], v[b]);
						swap(v[a-1], v[b-1]);
					}
				}
			}
		}
 
		if (s != 0) cout << "NO\n";
		else cout << "YES\n";
	}
}

Test 1

Group: 1, 2

Verdict: WRONG ANSWER

Test 2

Group: 2

Verdict: WRONG ANSWER

Test 3

Group: 1, 2

Verdict: WRONG ANSWER

Test 4

Group: 1, 2

Verdict: WRONG ANSWER