Test/CF/CF1015-C.test.cpp

• View this file on GitHub
• Last update: 2025-04-06 19:32:49+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://codeforces.com/contest/2084/problem/C
• Link: https://codeforces.com/contest/2084/submission/314231212

Depends on

• Permutationを $N-1$ 回以下のswapでソートする (Src/Sequence/PermutationSwapSort.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
// #define PROBLEM "https://codeforces.com/contest/2084/problem/C"
/*
 * Teza Round 1 (Codeforces Round 1015, Div. 1 + Div. 2) C. You Soared Afar With Grace
 * https://codeforces.com/contest/2084/submission/314231212
 */
#include "../../Src/Sequence/PermutationSwapSort.hpp"
#include <iostream>
int N, A[200020], B[200020], invA[200020];
void solve() {
    std::cin >> N;
    for (int i = 0 ; i < N ; i++) {
        std::cin >> A[i];
        invA[--A[i]] = i;
    }
    for (int i = 0 ; i < N ; i++) {
        std::cin >> B[i];
        B[i]--;
    }
    int same = 0;
    for (int i = 0 ; i < N ; i++) {
        if (A[i] == B[i]) same++;
        else {
            int id = invA[B[i]];
            if (B[id] != A[i]) {
                std::cout << -1 << '\n';
                return;
            }
        }
    }
    if (same != (N & 1)) {
        std::cout << -1 << '\n';
        return;
    }
    int L = 0, R = N - 1;
    std::vector<int> P(N, -1);
    for (int i = 0 ; i < N ; i++) if (P[i] == -1) {
        if (A[i] == B[i]) {
            P[i] = N / 2;
        }
        else {
            int j = invA[B[i]];
            assert(P[j] == -1);
            P[i] = L++;
            P[j] = R--;
        }
    }
    auto ans = zawa::PermutationSwapSort(P.begin(), P.end());
    std::cout << ans.size() << '\n';
    for (auto [i, j] : ans) std::cout << i + 1 << ' ' << j + 1 << '\n';
}
int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T;
    std::cin >> T;
    while (T--) solve();
#else
    std::cout << "Hello World\n";
#endif
}

#line 1 "Test/CF/CF1015-C.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
// #define PROBLEM "https://codeforces.com/contest/2084/problem/C"
/*
 * Teza Round 1 (Codeforces Round 1015, Div. 1 + Div. 2) C. You Soared Afar With Grace
 * https://codeforces.com/contest/2084/submission/314231212
 */
#line 2 "Src/Sequence/PermutationSwapSort.hpp"

#include <cassert>
#include <concepts>
#include <iterator>
#include <utility>
#include <vector>

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 10 "Src/Sequence/PermutationSwapSort.hpp"

namespace zawa {

namespace internal {

// Is A permutation of (0,1,...,|A|-1) ?
template <std::integral T>
bool IsPermutation(const std::vector<T>& A) {
    std::vector<bool> app(A.size());
    for (T v : A) {
        if (v < 0 or v >= (T)A.size()) return false;
        if (app[v]) return false;
        app[v] = true;
    }
    return true;
}

} // namespace internal

template <std::input_iterator It>
std::vector<std::pair<usize, usize>> PermutationSwapSort(It first, It last) {
    std::vector P(first, last);
    assert(internal::IsPermutation(P));
    std::vector<std::pair<usize, usize>> res;
    for (usize i = 0 ; i < P.size() ; i++) while ((usize)P[i] != i) {
        res.push_back({i, P[i]});
        std::swap(P[i], P[P[i]]);
    }
    return res;
}

} // namespace zawa
#line 8 "Test/CF/CF1015-C.test.cpp"
#include <iostream>
int N, A[200020], B[200020], invA[200020];
void solve() {
    std::cin >> N;
    for (int i = 0 ; i < N ; i++) {
        std::cin >> A[i];
        invA[--A[i]] = i;
    }
    for (int i = 0 ; i < N ; i++) {
        std::cin >> B[i];
        B[i]--;
    }
    int same = 0;
    for (int i = 0 ; i < N ; i++) {
        if (A[i] == B[i]) same++;
        else {
            int id = invA[B[i]];
            if (B[id] != A[i]) {
                std::cout << -1 << '\n';
                return;
            }
        }
    }
    if (same != (N & 1)) {
        std::cout << -1 << '\n';
        return;
    }
    int L = 0, R = N - 1;
    std::vector<int> P(N, -1);
    for (int i = 0 ; i < N ; i++) if (P[i] == -1) {
        if (A[i] == B[i]) {
            P[i] = N / 2;
        }
        else {
            int j = invA[B[i]];
            assert(P[j] == -1);
            P[i] = L++;
            P[j] = R--;
        }
    }
    auto ans = zawa::PermutationSwapSort(P.begin(), P.end());
    std::cout << ans.size() << '\n';
    for (auto [i, j] : ans) std::cout << i + 1 << ' ' << j + 1 << '\n';
}
int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T;
    std::cin >> T;
    while (T--) solve();
#else
    std::cout << "Hello World\n";
#endif
}

Back to top page