Submission #1241618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241618		giorgi123glm	Cat (info1cup19_cat)	C++20	40 / 100	162 ms	3968 KiB

cat

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

#include <functional>
#include <iostream>
#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;
                }
            
            int cnt_bad = 0;
            vector <bool> been (N + 1);
            function <void(int)> dfs = [&](int p) {
                been[p] = 1;

                if (bad[p])
                    cnt_bad++;

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

            int odd_cnt = 0;
            int comp_cnt = 0;
            for (int i = 1; i <= N / 2; i++)
                if (!been[i]) {
                    cnt_bad = 0;
                    dfs (i);

                    if (cnt_bad % 2 == 1) {
                        odd_cnt++;
                    }
                    comp_cnt++;
                }
            
            if (odd_cnt % 2 == 1) {
                cout << -1 << '\n';
                return;
            }

            cout << N / 2 + (odd_cnt / 2) - (comp_cnt - odd_cnt / 2) << ' ' << 0 << '\n';
        }();
}

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