oj.uz

Submission #675685

# Submission time Handle Problem Language Result Execution time Memory
675685 2022-12-27T17:59:32 Z vovamr Cat (info1cup19_cat) C++17
100 / 100
 427 ms 27540 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline void solve() {
	int n;
	cin >> n;
	ve<int> p(n);
	for (auto &i : p) cin >> i;

	for (int i = 0; i < n; ++i) {
		if (p[i] + p[n - i - 1] != n + 1) {
			return void(cout << -1 << '\n');
		}
	}

	ve<pii> answer;

	ve<int> pos(n + 1);
	for (int i = 0; i < n; ++i) pos[p[i]] = i;

	for (int i = 0; i < n / 2; ++i) {
		if (p[i] != i + 1 && pos[i + 1] != n - i - 1) {

			int a = i;
			int b = pos[i + 1];

			answer.pb({ i, pos[i + 1] });

			swap(p[a], p[b]);
			swap(p[n - a - 1], p[n - b - 1]);

			swap(pos[p[a]], pos[p[b]]);
			swap(pos[p[n - a - 1]], pos[p[n - b - 1]]);
		}
	}

	int cnt = 0;
	for (int i = 0; i < n / 2; ++i) {
		assert(p[i] == i + 1 || p[i] == n + 1 - (i + 1));
		cnt += (p[i] == n + 1 - (i + 1));
	}

	if (cnt & 1) {
		return void(cout << -1 << '\n');
	}

	ve<int> bad;
	for (int i = 0; i < n / 2; ++i) {
		if (p[i] == n + 1 - (i + 1)) {
			bad.pb(i);
		}
	}

	for (int i = 0; i < sz(bad); i += 2) {
		int a = bad[i];
		int b = bad[i + 1];

		answer.pb({n - a - 1, b});

		swap(p[n - a - 1], p[b]);
		swap(p[n - (n - a - 1) - 1], p[n - b - 1]);

		answer.pb({a, b});

		swap(p[a], p[b]);
		swap(p[n - a - 1], p[n - b - 1]);
	}

	cout << sz(answer) << " " << sz(answer) << '\n';
	for (auto &[i, j] : answer) cout << i + 1 << " " << j + 1 << '\n';

#ifdef LOCAL
	cout << "! "; for (auto &x : p) cout << x << " ";
	cout << "!" << '\n';
#endif
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 524 KB Output is correct
2 Correct 17 ms 460 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 18 ms 524 KB Output is correct
3 Correct 17 ms 460 KB Output is correct
4 Correct 26 ms 1088 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 8 ms 468 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 524 KB Output is correct
2 Correct 17 ms 460 KB Output is correct
3 Correct 392 ms 12488 KB Output is correct
4 Correct 370 ms 10884 KB Output is correct
5 Correct 418 ms 13356 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 18 ms 524 KB Output is correct
3 Correct 17 ms 460 KB Output is correct
4 Correct 26 ms 1088 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 8 ms 468 KB Output is correct
7 Correct 392 ms 12488 KB Output is correct
8 Correct 370 ms 10884 KB Output is correct
9 Correct 418 ms 13356 KB Output is correct
10 Correct 385 ms 25048 KB Output is correct
11 Correct 358 ms 23080 KB Output is correct
12 Correct 383 ms 26256 KB Output is correct
13 Correct 427 ms 27540 KB Output is correct
14 Correct 370 ms 26172 KB Output is correct