oj.uz

Submission #401046

# Submission time Handle Problem Language Result Execution time Memory
401046 2021-05-09T09:09:54 Z dolphingarlic Cat (info1cup19_cat) C++14
100 / 100
 524 ms 27428 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, a[200001];
bool inverted[200001], visited[200001];
vector<pair<int, int>> moves;

void swp(int x, int y) {
    moves.push_back({x, y});
    swap(a[x], a[y]);
    swap(a[n - x + 1], a[n - y + 1]);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        int inv_cnt = 0;
        bool possible = true;
        for (int i = 1; i <= n / 2; i++) {
            possible &= a[i] + a[n - i + 1] == n + 1;
            inverted[i] = a[i] > a[n - i + 1];
            inv_cnt += inverted[i];
            visited[i] = false;
        }
        if ((inv_cnt & 1) || !possible) {
            cout << "-1\n";
            continue;
        }

        moves.clear();
        vector<int> unresolved;
        int opt = n / 2;
        for (int i = 1; i <= n / 2; i++) if (!visited[i]) {
            opt--;
            int curr = i, prv_inv = 0;
            while (!visited[curr]) {
                visited[curr] = true;
                if (inverted[curr]) {
                    if (prv_inv) {
                        swp(curr, n - prv_inv + 1);
                        curr = prv_inv;
                        prv_inv = 0;
                    } else prv_inv = curr;
                }
                curr = min(a[curr], a[n - curr + 1]);
            }
            if (prv_inv) unresolved.push_back(prv_inv);
        }
        for (int i = 0; i < unresolved.size(); i += 2) {
            opt += 2;
            swp(unresolved[i], n - unresolved[i + 1] + 1);
        }

        for (int i = 1; i <= n / 2; i++) {
            int curr = i;
            while (a[curr] != i) swp(curr, a[curr]);
        }
        
        cout << opt << ' ' << moves.size() << '\n';
        for (pair<int, int> i : moves)
            cout << i.first << ' ' << i.second << '\n';
    }
    return 0;
}

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int i = 0; i < unresolved.size(); i += 2) {
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 964 KB Output is correct
2 Correct 22 ms 948 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 23 ms 964 KB Output is correct
3 Correct 22 ms 948 KB Output is correct
4 Correct 25 ms 976 KB Output is correct
5 Correct 11 ms 600 KB Output is correct
6 Correct 8 ms 540 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 964 KB Output is correct
2 Correct 22 ms 948 KB Output is correct
3 Correct 491 ms 25028 KB Output is correct
4 Correct 477 ms 24316 KB Output is correct
5 Correct 524 ms 26220 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 23 ms 964 KB Output is correct
3 Correct 22 ms 948 KB Output is correct
4 Correct 25 ms 976 KB Output is correct
5 Correct 11 ms 600 KB Output is correct
6 Correct 8 ms 540 KB Output is correct
7 Correct 491 ms 25028 KB Output is correct
8 Correct 477 ms 24316 KB Output is correct
9 Correct 524 ms 26220 KB Output is correct
10 Correct 499 ms 23652 KB Output is correct
11 Correct 458 ms 22016 KB Output is correct
12 Correct 490 ms 26236 KB Output is correct
13 Correct 520 ms 27428 KB Output is correct
14 Correct 484 ms 26052 KB Output is correct