oj.uz

Submission #922608

# Submission time Handle Problem Language Result Execution time Memory
922608 2024-02-05T19:29:05 Z maxFedorchuk Cat (info1cup19_cat) C++17
100 / 100
 305 ms 31568 KB 
#include "bits/stdc++.h"
using namespace std;
 
const long long MX=2e5+10;
 
int a[MX];
int p[MX];
 
pair < int , int > vp1[MX];
pair < int , int > vp2[MX];
 
int n;
 
void swp(int i,int j) {
    swap(a[i], a[j]);
    swap(p[a[i]], p[a[j]]);
 
    swap(a[n - i + 1], a[n - j + 1]);
    swap(p[a[n - i + 1]], p[a[n - j + 1]]);
}
 
void fun() {
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[a[i]] = i;
    }
 
    for (int i = 1; i <= n / 2; i++) {
        if (a[i] + a[n - i + 1] != (n + 1)) {
            cout << "-1\n";
            return;
        }
    }
 
    int o1 = 0, o2 = 0;
    for (int i = 1; i <= n / 2; i++) {
        if (a[i] == i) {
            continue;
        }
 
        if (a[i] == (n - i + 1)) {
            vp1[++o1] = make_pair(i, n - i + 1);
        } else {
            vp2[++o2] = make_pair(i, p[i]);
            swp(i, p[i]);
        }
    }
 
    if (o1 & 1) {
        cout << "-1\n";
        return;
    }
 
    while (o1) {
        vp2[++o2] = make_pair(vp1[o1].first, vp1[o1 - 1].first);
        vp2[++o2] = make_pair(vp1[o1].first, vp1[o1 - 1].second);
        o1 -= 2;
    }
 
    cout << o2 << " " << o2 << "\n";
 
    for (int i = 1; i <= o2; i++) {
        cout << vp2[i].first << " " << vp2[i].second << "\n";
    }
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        fun();
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2652 KB Output is correct
2 Correct 13 ms 2724 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 13 ms 2652 KB Output is correct
3 Correct 13 ms 2724 KB Output is correct
4 Correct 15 ms 5208 KB Output is correct
5 Correct 6 ms 4696 KB Output is correct
6 Correct 5 ms 4700 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2652 KB Output is correct
2 Correct 13 ms 2724 KB Output is correct
3 Correct 295 ms 16464 KB Output is correct
4 Correct 280 ms 15004 KB Output is correct
5 Correct 289 ms 17200 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 13 ms 2652 KB Output is correct
3 Correct 13 ms 2724 KB Output is correct
4 Correct 15 ms 5208 KB Output is correct
5 Correct 6 ms 4696 KB Output is correct
6 Correct 5 ms 4700 KB Output is correct
7 Correct 295 ms 16464 KB Output is correct
8 Correct 280 ms 15004 KB Output is correct
9 Correct 289 ms 17200 KB Output is correct
10 Correct 286 ms 28860 KB Output is correct
11 Correct 276 ms 26828 KB Output is correct
12 Correct 291 ms 30264 KB Output is correct
13 Correct 305 ms 31568 KB Output is correct
14 Correct 289 ms 29712 KB Output is correct