Test/AtCoder/abc213_c.test.cpp

View this file on GitHub
Last update: 2025-03-04 23:23:46+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Link: https://atcoder.jp/contests/abc213/submissions/63197885
Link: https://atcoder.jp/contests/abc213/tasks/abc213_c

Depends on

Code

// #define PROBLEM "https://atcoder.jp/contests/abc213/tasks/abc213_c"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Sequence/CompressedSequence.hpp"
#include "../../Src/Template/TypeAlias.hpp"

/*
 * ABC213-C Reorder Cards
 * https://atcoder.jp/contests/abc213/submissions/63197885
 */

#include <iostream>
#include <vector>

using namespace zawa;

i32 main() {
#ifdef ATCODER
    usize H, W, N;
    std::cin >> H >> W >> N; 
    std::vector<u32> A(N), B(N);
    for (u32 i = 0 ; i < N ; i++) {
        std::cin >> A[i] >> B[i];
    }

    CompressedSequence compY(A);
    CompressedSequence<u32> compX(B.begin(), B.end());
    for (u32 i = 0 ; i < N ; i++) {
        std::cout << compY.map(i) + 1 << ' ' << compX.map(i) + 1 << std::endl;
    }
#else
    std::cout << "Hello World" << '\n';
#endif
}

#line 1 "Test/AtCoder/abc213_c.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc213/tasks/abc213_c"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Sequence/CompressedSequence.hpp"

#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 4 "Src/Sequence/CompressedSequence.hpp"

#include <vector>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa
#line 6 "Test/AtCoder/abc213_c.test.cpp"

/*
 * ABC213-C Reorder Cards
 * https://atcoder.jp/contests/abc213/submissions/63197885
 */

#include <iostream>
#line 14 "Test/AtCoder/abc213_c.test.cpp"

using namespace zawa;

i32 main() {
#ifdef ATCODER
    usize H, W, N;
    std::cin >> H >> W >> N; 
    std::vector<u32> A(N), B(N);
    for (u32 i = 0 ; i < N ; i++) {
        std::cin >> A[i] >> B[i];
    }

    CompressedSequence compY(A);
    CompressedSequence<u32> compX(B.begin(), B.end());
    for (u32 i = 0 ; i < N ; i++) {
        std::cout << compY.map(i) + 1 << ' ' << compX.map(i) + 1 << std::endl;
    }
#else
    std::cout << "Hello World" << '\n';
#endif
}