oj.uz

Submission #754683

# Submission time Handle Problem Language Result Execution time Memory
754683 2023-06-08T10:56:10 Z Stickfish Cat (info1cup19_cat) C++17
51.25 / 100
 513 ms 20552 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 340 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 756 KB Output is correct
2 Correct 19 ms 748 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 340 KB Valid reconstruction
2 Correct 23 ms 756 KB Output is correct
3 Correct 19 ms 748 KB Output is correct
4 Partially correct 24 ms 816 KB Valid reconstruction
5 Partially correct 9 ms 596 KB Valid reconstruction
6 Partially correct 8 ms 588 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 756 KB Output is correct
2 Correct 19 ms 748 KB Output is correct
3 Correct 436 ms 13692 KB Output is correct
4 Correct 407 ms 11716 KB Output is correct
5 Correct 477 ms 14384 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 340 KB Valid reconstruction
2 Correct 23 ms 756 KB Output is correct
3 Correct 19 ms 748 KB Output is correct
4 Partially correct 24 ms 816 KB Valid reconstruction
5 Partially correct 9 ms 596 KB Valid reconstruction
6 Partially correct 8 ms 588 KB Valid reconstruction
7 Correct 436 ms 13692 KB Output is correct
8 Correct 407 ms 11716 KB Output is correct
9 Correct 477 ms 14384 KB Output is correct
10 Partially correct 460 ms 15460 KB Valid reconstruction
11 Partially correct 454 ms 12852 KB Valid reconstruction
12 Partially correct 437 ms 17032 KB Valid reconstruction
13 Partially correct 513 ms 20552 KB Valid reconstruction
14 Partially correct 456 ms 17392 KB Valid reconstruction