Submission #1241639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241639		giorgi123glm	Cat (info1cup19_cat)	C++20	100 / 100	292 ms	13076 KiB

cat

// yes, i cat-ed "mkinitcpio.conf" file
// c: computer
// a: aided
// t: translation

#include <functional>
#include <iostream>
#include <sys/select.h>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int t = 0;
    cin >> t;

    while (t--)
        []()->void {
            int N = 0;
            cin >> N;

            vector <int> v (N + 1);
            for (int i = 1; i <= N; i++)
                cin >> v[i];

            for (int i = 1; i <= N; i++)
                if (v[i] + v[N - i + 1] != N + 1) {
                    cout << -1 << '\n';
                    return;
                }
            
            vector <bool> bad (N + 1);
            for (int i = 1; i <= N; i++)
                if (v[i] > N / 2) {
                    v[i] = N - v[i] + 1;
                    bad[i] = 1;
                }

            vector <pair <int, int> > movs;
            
            vector <int> cnt_bad;
            int join = -1;
            vector <bool> been (N + 1);
            function <void(int)> dfs = [&](int p) {
                been[p] = 1;

                if (bad[p]) {
                    cnt_bad.emplace_back (p);
                    join = p;
                }

                if (!been[v[p]])
                    dfs (v[p]);
            };

            vector <int> odd_cnt;
            int ans = 0;
            for (int i = 1; i <= N / 2; i++)
                if (!been[i]) {
                    cnt_bad = {}, join = -1;
                    dfs (i);

                    if (cnt_bad.size() % 2 == 1)
                        odd_cnt.emplace_back (join);
                }
            
            if (odd_cnt.size() % 2 == 1) {
                cout << -1 << '\n';
                return;
            }

            for (int i = 0; i < odd_cnt.size(); i += 2) {
                movs.emplace_back (odd_cnt[i], N - odd_cnt[i + 1] + 1);
                bad[odd_cnt[i]] = 0;
                bad[odd_cnt[i + 1]] = 0;
                swap (v[odd_cnt[i]], v[odd_cnt[i + 1]]);
            }

            been = vector <bool> (N + 1);
            for (int i = 1; i <= N / 2; i++)
                if (!been[i]) {
                    cnt_bad = {}, join = -1;
                    dfs (i);

                    if (cnt_bad.size() % 2 == 1)
                        exit (1);
                    for (int i = 0; i < cnt_bad.size(); i += 2) {
                        movs.emplace_back (cnt_bad[i], N - cnt_bad[i + 1] + 1);
                        bad[cnt_bad[i]] = 0;
                        bad[cnt_bad[i + 1]] = 0;
                        swap (v[cnt_bad[i]], v[cnt_bad[i + 1]]);
                    }
                }

            vector <bool> fixed (N + 1);
            for (int i = 1; i <= N / 2; i++)
                if (!fixed[i]) {
                    while (v[i] != i) {
                        fixed[v[i]] = 1;
                        movs.emplace_back (i, v[i]);
                        v[i] = v[v[i]];
                    }
                }

            cout << movs.size() << ' ' << movs.size() << '\n';
            for (auto [a, b] : movs)
                cout << a << ' ' << b << '\n';
        }();
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 35 / 35