oj.uz

Submission #924665

# Submission time Handle Problem Language Result Execution time Memory
924665 2024-02-09T11:42:32 Z Ianis Cat (info1cup19_cat) C++17
100 / 100
 352 ms 33000 KB 
#ifdef LOCAL
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <random>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define cerr if (false) cerr 
#define endl '\n'
#endif

#define fi first
#define se second

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))

#define bit(mask, i) (((mask) >> (i)) & 1)
#define popcount(x) __builtin_popcount(x)

#define YES cout << "YES" << endl
#define NO cout << "NO" << endl

using namespace std;

template <typename T>
bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
template <typename T>
bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 3e6+5;

int n;
int a[NMAX];
int pos[NMAX];
vector<pii> ans;
vector<pii> bad;

void read() {
   cin >> n;
   for (int i = 1; i <= n; i++) {
      cin >> a[i];
      pos[a[i]] = i;
   }
}

void my_swap(int i, int j) {
   ans.push_back({ i, j });

   swap(pos[a[i]], pos[a[j]]);
   swap(a[i], a[j]);

   swap(pos[a[n - i + 1]], pos[a[n - j + 1]]);
   swap(a[n - i + 1], a[n - j + 1]);
}

void solve() {
   ans.clear();
   bad.clear();

   for (int i = 1; i <= n / 2; i++) {
      if (a[i] != i) {
         if (a[i] == n - i + 1) {
            bad.push_back({ i, n - i + 1 });
         } else {
            my_swap(i, pos[i]);
         }
      }
   }


   for (int i = 0; i + 1 < int(bad.size()); i += 2) {
      my_swap(bad[i].fi, bad[i + 1].fi);
      my_swap(bad[i].fi, bad[i + 1].se);
   }

   for (int i = 1; i <= n; i++) {
      if (a[i] != i) {
         cout << -1 << endl;
         return;
      }
   }

   cout << ans.size() << ' ' << ans.size() << endl;
   for (auto &[ i, j ] : ans)
      cout << i << ' ' << j << endl;
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   
   int t = 1;
   cin >> t;

   while (t--) {
      read();
      solve();
   }

   return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3164 KB Output is correct
2 Correct 13 ms 3160 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 14 ms 3164 KB Output is correct
3 Correct 13 ms 3160 KB Output is correct
4 Correct 17 ms 3164 KB Output is correct
5 Correct 6 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3164 KB Output is correct
2 Correct 13 ms 3160 KB Output is correct
3 Correct 302 ms 24448 KB Output is correct
4 Correct 290 ms 22976 KB Output is correct
5 Correct 352 ms 25104 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 14 ms 3164 KB Output is correct
3 Correct 13 ms 3160 KB Output is correct
4 Correct 17 ms 3164 KB Output is correct
5 Correct 6 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 302 ms 24448 KB Output is correct
8 Correct 290 ms 22976 KB Output is correct
9 Correct 352 ms 25104 KB Output is correct
10 Correct 299 ms 27096 KB Output is correct
11 Correct 274 ms 27352 KB Output is correct
12 Correct 292 ms 33000 KB Output is correct
13 Correct 345 ms 31832 KB Output is correct
14 Correct 296 ms 32368 KB Output is correct