oj.uz

Submission #754571

# Submission time Handle Problem Language Result Execution time Memory
754571 2023-06-08T05:54:58 Z Stickfish Cat (info1cup19_cat) C++17
16 / 100
 1000 ms 4652 KB 
#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> sort_ops(vector<int> p) {
    int n = p.size();
    vector<pair<int, int>> ans;
    for (int t = 0; t < n; ++t) {
        if (p[t] == t)
            continue;
        for (int i = t + 1; i < n; ++i) if (p[i] == t) {
            ans.push_back({t, i});
            swap(p[i], p[t]);
            break;
        }
    }
    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 340 KB Correctly distinguished between possibility and impossibility

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1000 KB Output is correct
2 Correct 44 ms 936 KB Output is correct

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Correctly distinguished between possibility and impossibility
2 Correct 46 ms 1000 KB Output is correct
3 Correct 44 ms 936 KB Output is correct
4 Correct 37 ms 844 KB Correctly distinguished between possibility and impossibility
5 Correct 14 ms 508 KB Correctly distinguished between possibility and impossibility
6 Correct 13 ms 340 KB Correctly distinguished between possibility and impossibility

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1000 KB Output is correct
2 Correct 44 ms 936 KB Output is correct
3 Execution timed out 1049 ms 4652 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Correctly distinguished between possibility and impossibility
2 Correct 46 ms 1000 KB Output is correct
3 Correct 44 ms 936 KB Output is correct
4 Correct 37 ms 844 KB Correctly distinguished between possibility and impossibility
5 Correct 14 ms 508 KB Correctly distinguished between possibility and impossibility
6 Correct 13 ms 340 KB Correctly distinguished between possibility and impossibility
7 Execution timed out 1049 ms 4652 KB Time limit exceeded
8 Halted 0 ms 0 KB -