Submission #754683

#	Time	Username	Problem	Language	Result	Execution time	Memory
754683		Stickfish	Cat (info1cup19_cat)	C++17	51.25 / 100	513 ms	20552 KiB

cat

#include <iostream>
#include <cassert>
#include <vector>
using namespace std;

vector<pair<int, int>> sort_ops(vector<int> p) {
    int n = p.size();
    vector<int> rp(n);
    for (int i = 0; i < n; ++i)
        rp[p[i]] = i;
    vector<pair<int, int>> ans;
    for (int t = 0; t < n; ++t) {
        if (p[t] == t)
            continue;
        int i = rp[t];
        ans.push_back({t, i});
        swap(p[i], p[t]);
        rp[p[t]] = t;
        rp[p[i]] = i;
    }
    return ans;
}

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<pair<int, int>> ans;
    for (int t = 0; t < n / 2; ++t) {
        if (p[t] == t || p[t] >= n / 2)
            continue;
        int i = rp[t];
        ans.push_back({t, i});
        //cout << "! " << t << ' ' << i << ": " << p[t] << ' ' << p[i] << endl;
        swap(p[i], p[t]);
        swap(p[n - 1 - i], p[n - 1 - t]);
        rp[p[t]] = t;
        rp[p[i]] = i;
    }
    //for (int i = 0; i < n; ++i)
        //cout << p[i] << ' ';
    //cout << endl;
    vector<int> prp(n / 2);
    for (int i = 0; i < n / 2; ++i) {
        if (p[i] == i)
            prp[i] = i;
        else {
            assert(p[i] >= n / 2);
            prp[i] = n - 1 - p[i];
        }
    }
    vector<int> singles;
    for (int i = 0; i < n / 2; ++i) {
        if (p[i] == i)
            continue;
        if (prp[i] == i) {
            singles.push_back(i);
            continue;
        }
        int j = i;
        vector<int> a;
        do { 
            a.push_back(j);
            j = prp[j];
        } while (j != i);
        //cout << i << ": ";
        //for (auto x : a)
            //cout << x << ' ';
        //cout << endl;
        for (size_t t = 1; t < a.size(); ++t) {
            swap(prp[a[0]], prp[a[t]]);
            swap(p[a[0]], p[n - 1 - a[t]]);
            swap(p[a[t]], p[n - 1 - a[0]]);
            ans.push_back({a[0], n - 1 - a[t]});
        }
    }
    while (singles.size()) {
        int i = singles.back();
        singles.pop_back();
        int j = singles.back();
        singles.pop_back();
        ans.push_back({i, n - 1 - j});
        ans.push_back({i, 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";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 5.25 / 15
• Subtask 2: 10 / 10
• Subtask 3: 8.75 / 25
• Subtask 4: 15 / 15
• Subtask 5: 12.25 / 35