Submission #675682

#TimeUsernameProblemLanguageResultExecution timeMemory
675682vovamrCat (info1cup19_cat)C++17
25 / 100
417 ms27940 KiB
#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); } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...