oj.uz

Submission #1100770

# Submission time Handle Problem Language Result Execution time Memory
1100770 2024-10-14T15:59:14 Z Kirill22 Cat (info1cup19_cat) C++17
51.25 / 100
 308 ms 28912 KB 
#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), pos(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        pos[a[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        if (n - pos[i] - 1 != pos[n - i - 1]) {
            cout << -1 << '\n';
            return;
        }
    }
    vector<pair<int, int>> ans;
    auto Swap = [&] (int i, int j) {
        swap(a[i], a[j]);
        pos[a[i]] = i;
        pos[a[j]] = j;
    };
    auto make = [&] (int i, int j) {
        ans.push_back({i, j});
        Swap(i, j);
        Swap(n - i - 1, n - j - 1);
    };
    for (int l = 0; l < n - 1 - l; l++) {
        int r = n - l - 1;
        if (a[l] == l && a[r] == r) {
            continue;
        }
        if (a[l] == l || a[r] == r) {
            assert(false);
            if (r - l + 1 <= 5) {
                cout << -1 << '\n';
                return;
            }
            if (a[l] == l) {
                int ps = l + 1;
                while (a[ps] == r || a[n - ps - 1] == r) ps++;
                make(l, ps);
            } else {
                int ps = l + 1;
                while (a[ps] == l || a[n - ps - 1] == l) ps++;
                make(r, ps);
            }
        }
        assert(a[l] != l && a[r] != r);
        if (pos[l] != n - 1 - pos[r]) {
            assert(false);
        }
        if (a[l] == r) {
            assert(a[r] == l);
            if (l + 1 == r) {
                cout << -1 << '\n';
                return;
            }
            make(l, l + 1);
        }
        make(l, pos[l]);
        assert(a[l] == l && a[r] == r);
    }
    cout << ans.size() << " " << ans.size() << '\n';
    for (auto [i, j] : ans) {
        cout << i + 1 << " " << j + 1 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    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 13 ms 1272 KB Output is correct
2 Correct 13 ms 1108 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 13 ms 1272 KB Output is correct
3 Correct 13 ms 1108 KB Output is correct
4 Partially correct 15 ms 1108 KB Valid reconstruction
5 Partially correct 6 ms 756 KB Valid reconstruction
6 Partially correct 6 ms 596 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1272 KB Output is correct
2 Correct 13 ms 1108 KB Output is correct
3 Correct 306 ms 27712 KB Output is correct
4 Correct 290 ms 26376 KB Output is correct
5 Correct 305 ms 28348 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 13 ms 1272 KB Output is correct
3 Correct 13 ms 1108 KB Output is correct
4 Partially correct 15 ms 1108 KB Valid reconstruction
5 Partially correct 6 ms 756 KB Valid reconstruction
6 Partially correct 6 ms 596 KB Valid reconstruction
7 Correct 306 ms 27712 KB Output is correct
8 Correct 290 ms 26376 KB Output is correct
9 Correct 305 ms 28348 KB Output is correct
10 Partially correct 299 ms 25492 KB Valid reconstruction
11 Partially correct 258 ms 23688 KB Valid reconstruction
12 Partially correct 267 ms 27348 KB Valid reconstruction
13 Partially correct 308 ms 28912 KB Valid reconstruction
14 Partially correct 287 ms 26544 KB Valid reconstruction