oj.uz

Submission #754721

# Submission time Handle Problem Language Result Execution time Memory
754721 2023-06-08T12:46:19 Z Stickfish Cat (info1cup19_cat) C++17
100 / 100
 471 ms 21256 KB 
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; ++i)
        cin >> p[i], --p[i];
    for (int i = 0; i < n; ++i) if (p[i] + p[n - i - 1] != n - 1) {
        cout << "-1\n";
        return;
    }
    int e1 = 0;
    for (int i = 0; i < n / 2; ++i)
        e1 += p[i] >= n / 2;
    if (e1 % 2) {
        cout << "-1\n";
        return;
    }

    vector<int> rp(n);
    for (int i = 0; i < n; ++i)
        rp[p[i]] = i;
    vector<int> pcp(n / 2);
    vector<bool> pcp_leap(n / 2);
    for (int  i = 0; i < n / 2; ++i) {
        if (p[i] < n / 2) {
            pcp[i] = p[i];
            pcp_leap[i] = 0;
        } else {
            pcp[i] = n - 1 - p[i];
            pcp_leap[i] = 1;
        }
    }
    vector<int> singles;
    vector<pair<int, int>> ans;
    for (int i = 0; i < n / 2; ++i) {
        if (p[i] == i)
            continue;
        if (pcp[i] == i) {
            singles.push_back(i);
            continue;
        }
        vector<int> a;
        int j = i;
        do {
            a.push_back(j);
            j = pcp[j];
        } while (j != i);
        bool xr = false;
        for (auto t : a)
            xr ^= pcp_leap[t];
        //for (auto x : a)
            //cout << x << ' ';
        //cout << " | " << xr << endl;
        if (xr) {
            a.clear();
            j = i;
            do {
                a.push_back(j);
                j = p[j];
            } while (j != i);

            for (size_t r = 0; r + 1 < a.size(); ++r) if (a[r + 1] + a[0] == n - 1) {
                ans.push_back({a[0], a[r]});
                swap(p[a[0]], p[a[r]]);
                swap(p[n - 1 - a[0]], p[n - 1 - a[r]]);
                singles.push_back(a[0]);
                for (size_t t = 2; t <= r; ++t) { 
                    ans.push_back({a[1], a[t]});
                    swap(p[a[1]], p[a[t]]);
                    swap(p[n - 1 - a[1]], p[n - 1 - a[t]]);
                }
                break;
            }
        } else {

            for (size_t t = 0; t + 1 < a.size(); ++t) {
                int i0 = a[0];
                int j0 = a[t + 1];
                xr ^= pcp_leap[a[t]];
                if (xr)
                    j0 = n - 1 - a[t + 1];
                ans.push_back({i0, j0});
                swap(p[i0], p[j0]);
                swap(p[n - 1 - i0], p[n - 1 - j0]);
            }
        }
    }

    while (singles.size()) {
        int i = singles.back();
        singles.pop_back();
        int j = singles.back();
        singles.pop_back();
        ans.push_back({i, n - 1 - j});
        swap(p[i], p[n - 1 - j]);
        swap(p[n - 1 - i], p[j]);
        ans.push_back({i, j});
        swap(p[i], p[j]);
        swap(p[n - 1 - i], p[n - 1 - j]);
        //cout << "{ " << i << ' ' << j << " }" << endl;
    }
    
    //if (e1 == 0) {
        //vector<int> p0(n / 2);
        //for (int i = 0; i < n / 2; ++i)
            //p0[i] = p[i];
    cout << ans.size() << ' ' << ans.size() << '\n';
    for (auto x : ans)
        cout << x.first + 1 << ' ' << x.second + 1 << '\n';
        //return;
    //}

    //cout << "1 1\n";
    //cout << "1 2\n";
    //for (int i = 0; i < n; ++i)
        //cout << p[i] << ' ';
    //cout << endl << endl;;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
        //cout << 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 19 ms 492 KB Output is correct
2 Correct 18 ms 536 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 19 ms 492 KB Output is correct
3 Correct 18 ms 536 KB Output is correct
4 Correct 22 ms 588 KB Output is correct
5 Correct 8 ms 468 KB Output is correct
6 Correct 6 ms 340 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 492 KB Output is correct
2 Correct 18 ms 536 KB Output is correct
3 Correct 405 ms 10220 KB Output is correct
4 Correct 384 ms 9548 KB Output is correct
5 Correct 423 ms 11244 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 19 ms 492 KB Output is correct
3 Correct 18 ms 536 KB Output is correct
4 Correct 22 ms 588 KB Output is correct
5 Correct 8 ms 468 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 405 ms 10220 KB Output is correct
8 Correct 384 ms 9548 KB Output is correct
9 Correct 423 ms 11244 KB Output is correct
10 Correct 434 ms 18548 KB Output is correct
11 Correct 401 ms 16880 KB Output is correct
12 Correct 468 ms 18636 KB Output is correct
13 Correct 471 ms 21256 KB Output is correct
14 Correct 466 ms 18892 KB Output is correct