제출 #1319046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319046		Ghulam_Junaid	Cat (info1cup19_cat)	C++20	100 / 100	252 ms	14180 KiB

cat

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    int a[n + 1], pos[n + 1] = {};
    for (int i = 1; i <= n; i ++)
        cin >> a[i], pos[a[i]] = i;

    vector<int> bad;
    vector<pair<int, int>> vec;
    for (int i = 1; i <= n / 2; i ++){
        if (pos[i] == i) continue;
        int p = pos[i];
        if (n - i + 1 == p){
            bad.push_back(i);
            continue;
        }

        vec.push_back({i, p});
        swap(a[p], a[i]);
        swap(pos[a[p]], pos[a[i]]);

        int o1 = n - i + 1;
        int o2 = n - p + 1;
        swap(a[o1], a[o2]);
        swap(pos[a[o1]], pos[a[o2]]);
    }

    while (bad.size() >= 2){
        int i = bad.back(); bad.pop_back();
        int p = bad.back(); bad.pop_back();

        p = n - p + 1;
        vec.push_back({i, p});

        swap(a[p], a[i]);
        swap(pos[a[p]], pos[a[i]]);

        int o1 = n - i + 1;
        int o2 = n - p + 1;
        swap(a[o1], a[o2]);
        swap(pos[a[o1]], pos[a[o2]]);

        p = n - p + 1;
        vec.push_back({i, p});

        swap(a[p], a[i]);
        swap(pos[a[p]], pos[a[i]]);

        o1 = n - i + 1;
        o2 = n - p + 1;
        swap(a[o1], a[o2]);
        swap(pos[a[o1]], pos[a[o2]]);
    }

    bool good = 1;
    for (int i = 1; i <= n; i ++)
        good &= (a[i] == i);

    if (!good){
        cout << -1 << '\n';
        return ;
    }

    cout << vec.size() << " " << vec.size() << '\n';
    for (auto [i, j] : vec)
        cout << i << " " << j << '\n';
}

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

    int t;
    cin >> t;

    while (t--)
        solve();
    return 0;
}

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