tests/multisort.test.cpp

• View this file on GitHub
• Last update: 2025-07-13 17:32:24+09:00

Depends on

• Assertion macro (tools/assert_that.hpp)
• std::less by key (tools/less_by.hpp)
• Sort multiple arrays at once (tools/multisort.hpp)

Code

// competitive-verifier: STANDALONE

#include <array>
#include <iostream>
#include <string>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/less_by.hpp"
#include "tools/multisort.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  {
    std::vector<int> a = {5, 2, 4, 3, 1};
    std::string b = "adbce";
    tools::multisort(a, b, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(b == "edcba");
  }
  {
    std::vector<int> a = {5, 2, 4, 3, 1};
    std::string b = "adbce";
    std::array<double, 5> c = {-5.0, -2.0, -4.0, -3.0, -1.0};
    tools::multisort(a, b, c, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(b == "edcba");
    assert_that(c == std::array<double, 5>{-1.0, -2.0, -3.0, -4.0, -5.0});
  }
  {
    std::vector<int> a = {5, 2, 4, 3, 1};
    std::string b = "adbce";
    std::array<double, 5> c = {-5.0, -2.0, -4.0, -3.0, -1.0};
    std::vector<int> d = {5, 2, 4, 3, 1};
    tools::multisort(a, b, c, d, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(b == "edcba");
    assert_that(c == std::array<double, 5>{-1.0, -2.0, -3.0, -4.0, -5.0});
    assert_that(d == std::vector<int>{1, 2, 3, 4, 5});
  }
  {
    std::vector<int> a = {5, 2, 4, 3, 1};
    std::string b = "adbce";
    std::array<double, 5> c = {-5.0, -2.0, -4.0, -3.0, -1.0};
    std::vector<int> d = {5, 2, 4, 3, 1};
    std::string e = "adbce";
    tools::multisort(a, b, c, d, e, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(b == "edcba");
    assert_that(c == std::array<double, 5>{-1.0, -2.0, -3.0, -4.0, -5.0});
    assert_that(d == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(e == "edcba");
  }
  {
    std::vector<int> a;
    std::string b;
    tools::multisort(a, b, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a.empty());
    assert_that(b.empty());
  }

  return 0;
}

#line 1 "tests/multisort.test.cpp"
// competitive-verifier: STANDALONE

#include <array>
#include <iostream>
#include <string>
#include <vector>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/less_by.hpp"



namespace tools {

  template <class F>
  class less_by {
  private:
    F selector;

  public:
    less_by(const F& selector) : selector(selector) {
    }

    template <class T>
    bool operator()(const T& x, const T& y) const {
      return selector(x) < selector(y);
    }
  };
}


#line 1 "tools/multisort.hpp"



#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <ranges>
#include <utility>
#line 11 "tools/multisort.hpp"

namespace tools {
  namespace detail {
    namespace multisort {
      template <::std::ranges::random_access_range R>
      void sort(R&& r, const ::std::vector<int>& p) {
        ::std::vector<::std::ranges::range_value_t<R>> sorted_r(p.size());
        for (int i = 0; i < ::std::ssize(p); ++i) {
          sorted_r[i] = ::std::move(::std::ranges::begin(r)[p[i]]);
        }
        ::std::ranges::move(sorted_r, ::std::ranges::begin(r));
      }
    }
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    ::std::ranges::random_access_range R3,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, R3&& r3, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);
    assert(::std::ranges::ssize(r3) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
    ::tools::detail::multisort::sort(::std::forward<R3>(r3), p);
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    ::std::ranges::random_access_range R3,
    ::std::ranges::random_access_range R4,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, R3&& r3, R4&& r4, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);
    assert(::std::ranges::ssize(r3) == n);
    assert(::std::ranges::ssize(r4) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
    ::tools::detail::multisort::sort(::std::forward<R3>(r3), p);
    ::tools::detail::multisort::sort(::std::forward<R4>(r4), p);
  }

  template <
    ::std::ranges::random_access_range R1,
    ::std::ranges::random_access_range R2,
    ::std::ranges::random_access_range R3,
    ::std::ranges::random_access_range R4,
    ::std::ranges::random_access_range R5,
    typename Comp
  > requires ::std::sortable<::std::vector<int>::iterator, Comp>
  void multisort(R1&& r1, R2&& r2, R3&& r3, R4&& r4, R5&& r5, const Comp comp) {
    const int n = ::std::ranges::size(r1);
    assert(::std::ranges::ssize(r2) == n);
    assert(::std::ranges::ssize(r3) == n);
    assert(::std::ranges::ssize(r4) == n);
    assert(::std::ranges::ssize(r5) == n);

    ::std::vector<int> p(n);
    ::std::iota(p.begin(), p.end(), 0);
    ::std::ranges::sort(p, comp);

    ::tools::detail::multisort::sort(::std::forward<R1>(r1), p);
    ::tools::detail::multisort::sort(::std::forward<R2>(r2), p);
    ::tools::detail::multisort::sort(::std::forward<R3>(r3), p);
    ::tools::detail::multisort::sort(::std::forward<R4>(r4), p);
    ::tools::detail::multisort::sort(::std::forward<R5>(r5), p);
  }
}


#line 10 "tests/multisort.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  {
    std::vector<int> a = {5, 2, 4, 3, 1};
    std::string b = "adbce";
    tools::multisort(a, b, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(b == "edcba");
  }
  {
    std::vector<int> a = {5, 2, 4, 3, 1};
    std::string b = "adbce";
    std::array<double, 5> c = {-5.0, -2.0, -4.0, -3.0, -1.0};
    tools::multisort(a, b, c, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(b == "edcba");
    assert_that(c == std::array<double, 5>{-1.0, -2.0, -3.0, -4.0, -5.0});
  }
  {
    std::vector<int> a = {5, 2, 4, 3, 1};
    std::string b = "adbce";
    std::array<double, 5> c = {-5.0, -2.0, -4.0, -3.0, -1.0};
    std::vector<int> d = {5, 2, 4, 3, 1};
    tools::multisort(a, b, c, d, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(b == "edcba");
    assert_that(c == std::array<double, 5>{-1.0, -2.0, -3.0, -4.0, -5.0});
    assert_that(d == std::vector<int>{1, 2, 3, 4, 5});
  }
  {
    std::vector<int> a = {5, 2, 4, 3, 1};
    std::string b = "adbce";
    std::array<double, 5> c = {-5.0, -2.0, -4.0, -3.0, -1.0};
    std::vector<int> d = {5, 2, 4, 3, 1};
    std::string e = "adbce";
    tools::multisort(a, b, c, d, e, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(b == "edcba");
    assert_that(c == std::array<double, 5>{-1.0, -2.0, -3.0, -4.0, -5.0});
    assert_that(d == std::vector<int>{1, 2, 3, 4, 5});
    assert_that(e == "edcba");
  }
  {
    std::vector<int> a;
    std::string b;
    tools::multisort(a, b, tools::less_by([&](const int i) { return a[i]; }));
    assert_that(a.empty());
    assert_that(b.empty());
  }

  return 0;
}

Back to top page