oj.uz

Submission #754717

# Submission time Handle Problem Language Result Execution time Memory
754717 2023-06-08T12:41:03 Z Stickfish Cat (info1cup19_cat) C++17
31 / 100
 516 ms 262144 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 + 1]];
                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
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Correctly distinguished between possibility and impossibility

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 468 KB Output is correct
2 Correct 18 ms 532 KB Output is correct

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Correctly distinguished between possibility and impossibility
2 Correct 19 ms 468 KB Output is correct
3 Correct 18 ms 532 KB Output is correct
4 Correct 57 ms 1952 KB Correctly distinguished between possibility and impossibility
5 Correct 51 ms 2472 KB Correctly distinguished between possibility and impossibility
6 Correct 40 ms 2600 KB Correctly distinguished between possibility and impossibility

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 468 KB Output is correct
2 Correct 18 ms 532 KB Output is correct
3 Correct 432 ms 17172 KB Output is correct
4 Correct 409 ms 17596 KB Output is correct
5 Correct 447 ms 19228 KB Output is correct

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Correctly distinguished between possibility and impossibility
2 Correct 19 ms 468 KB Output is correct
3 Correct 18 ms 532 KB Output is correct
4 Correct 57 ms 1952 KB Correctly distinguished between possibility and impossibility
5 Correct 51 ms 2472 KB Correctly distinguished between possibility and impossibility
6 Correct 40 ms 2600 KB Correctly distinguished between possibility and impossibility
7 Correct 432 ms 17172 KB Output is correct
8 Correct 409 ms 17596 KB Output is correct
9 Correct 447 ms 19228 KB Output is correct
10 Runtime error 516 ms 262144 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -