oj.uz

Submission #1100772

# Submission time Handle Problem Language Result Execution time Memory
1100772 2024-10-14T16:09:40 Z Kirill22 Cat (info1cup19_cat) C++17
100 / 100
 322 ms 13860 KB 
#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), pos(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        pos[a[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        if (n - pos[i] - 1 != pos[n - i - 1]) {
            cout << -1 << '\n';
            return;
        }
    }
    vector<pair<int, int>> ans;
    auto Swap = [&] (int i, int j) {
        swap(a[i], a[j]);
        pos[a[i]] = i;
        pos[a[j]] = j;
    };
    auto make = [&] (int i, int j) {
        ans.push_back({i, j});
        Swap(i, j);
        Swap(n - i - 1, n - j - 1);
    };
    bool optimal = true;
    if (optimal) {
        vector<int> todo;
        for (int it = 0; it < n / 2; it++) {
            if (a[it] != it && a[it] != n - it - 1) {
                make(it, pos[it]);
            }
            if (a[it] == it) {
                continue;
            }
            if (a[it] == n - it - 1) {
                todo.push_back(it);
                continue;
            }
        }
        if ((int) todo.size() % 2) {
            cout << -1 << '\n';
            return;
        }
        for (int i = 0; i < (int) todo.size(); i += 2) {
            make(pos[todo[i]], pos[n - todo[i + 1] - 1]);
            make(pos[todo[i]], pos[todo[i + 1]]);
        }
    }
    for (int l = 0; l < n - 1 - l && !optimal; l++) {
        int r = n - l - 1;
        if (a[l] == l && a[r] == r) {
            continue;
        }
        if (a[l] == l || a[r] == r) {
            assert(false);
            if (r - l + 1 <= 5) {
                cout << -1 << '\n';
                return;
            }
            if (a[l] == l) {
                int ps = l + 1;
                while (a[ps] == r || a[n - ps - 1] == r) ps++;
                make(l, ps);
            } else {
                int ps = l + 1;
                while (a[ps] == l || a[n - ps - 1] == l) ps++;
                make(r, ps);
            }
        }
        assert(a[l] != l && a[r] != r);
        if (pos[l] != n - 1 - pos[r]) {
            assert(false);
        }
        if (a[l] == r) {
            assert(a[r] == l);
            if (l + 1 == r) {
                cout << -1 << '\n';
                return;
            }
            make(l, l + 1);
        }
        make(l, pos[l]);
        assert(a[l] == l && a[r] == r);
    }
    cout << ans.size() << " " << ans.size() << '\n';
    for (auto [i, j] : ans) {
        cout << i + 1 << " " << j + 1 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 616 KB Output is correct
2 Correct 15 ms 620 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Output is correct
2 Correct 16 ms 616 KB Output is correct
3 Correct 15 ms 620 KB Output is correct
4 Correct 13 ms 592 KB Output is correct
5 Correct 6 ms 608 KB Output is correct
6 Correct 5 ms 336 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 616 KB Output is correct
2 Correct 15 ms 620 KB Output is correct
3 Correct 277 ms 12956 KB Output is correct
4 Correct 269 ms 11428 KB Output is correct
5 Correct 284 ms 13860 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Output is correct
2 Correct 16 ms 616 KB Output is correct
3 Correct 15 ms 620 KB Output is correct
4 Correct 13 ms 592 KB Output is correct
5 Correct 6 ms 608 KB Output is correct
6 Correct 5 ms 336 KB Output is correct
7 Correct 277 ms 12956 KB Output is correct
8 Correct 269 ms 11428 KB Output is correct
9 Correct 284 ms 13860 KB Output is correct
10 Correct 300 ms 11616 KB Output is correct
11 Correct 278 ms 9440 KB Output is correct
12 Correct 322 ms 11808 KB Output is correct
13 Correct 321 ms 13600 KB Output is correct
14 Correct 287 ms 11204 KB Output is correct