oj.uz

Submission #754572

# Submission time Handle Problem Language Result Execution time Memory
754572 2023-06-08T05:57:37 Z Stickfish Cat (info1cup19_cat) C++17
36.25 / 100
 901 ms 17064 KB 
#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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 488 KB Output is correct
2 Correct 41 ms 472 KB Output is correct

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 212 KB Correctly distinguished between possibility and impossibility
2 Correct 44 ms 488 KB Output is correct
3 Correct 41 ms 472 KB Output is correct
4 Correct 32 ms 212 KB Correctly distinguished between possibility and impossibility
5 Correct 13 ms 212 KB Correctly distinguished between possibility and impossibility
6 Correct 12 ms 212 KB Correctly distinguished between possibility and impossibility

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 488 KB Output is correct
2 Correct 41 ms 472 KB Output is correct
3 Correct 877 ms 14692 KB Output is correct
4 Correct 876 ms 15364 KB Output is correct
5 Correct 901 ms 17064 KB Output is correct

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 212 KB Correctly distinguished between possibility and impossibility
2 Correct 44 ms 488 KB Output is correct
3 Correct 41 ms 472 KB Output is correct
4 Correct 32 ms 212 KB Correctly distinguished between possibility and impossibility
5 Correct 13 ms 212 KB Correctly distinguished between possibility and impossibility
6 Correct 12 ms 212 KB Correctly distinguished between possibility and impossibility
7 Correct 877 ms 14692 KB Output is correct
8 Correct 876 ms 15364 KB Output is correct
9 Correct 901 ms 17064 KB Output is correct
10 Correct 640 ms 3944 KB Correctly distinguished between possibility and impossibility
11 Correct 633 ms 3896 KB Correctly distinguished between possibility and impossibility
12 Correct 880 ms 4688 KB Correctly distinguished between possibility and impossibility
13 Correct 761 ms 4752 KB Correctly distinguished between possibility and impossibility
14 Correct 676 ms 4488 KB Correctly distinguished between possibility and impossibility