Submission #754572

#	Time	Username	Problem	Language	Result	Execution time	Memory
754572		Stickfish	Cat (info1cup19_cat)	C++17	36.25 / 100	901 ms	17064 KiB

cat

#include <iostream>
#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;
    }
    if (e1 == 0) {
        vector<int> p0(n / 2);
        for (int i = 0; i < n / 2; ++i)
            p0[i] = p[i];
        vector<pair<int, int>> ans = sort_ops(p0);
        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() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 2.25 / 15
• Subtask 2: 10 / 10
• Subtask 3: 3.75 / 25
• Subtask 4: 15 / 15
• Subtask 5: 5.25 / 35