proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/triangular_array.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE

#include <functional>
#include <iostream>
#include <sstream>
#include "tools/assert_that.hpp"
#include "tools/triangular_array.hpp"

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

  for (int n = 0; n <= 7; ++n) {
    {
      tools::triangular_array<int, std::less<int>> a(n, 0);
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          a[i][j] = k++;
        }
      }
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      std::stringstream ss;
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          ss << k++ << " \n"[j == n - 1];
        }
      }
      tools::triangular_array<int, std::less<int>> a(n);
      ss >> a;
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      tools::triangular_array<int, std::less_equal<int>> a(n, 0);
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
          a[i][j] = k++;
        }
      }
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      std::stringstream ss;
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
          ss << k++ << " \n"[j == n - 1];
        }
      }
      tools::triangular_array<int, std::less_equal<int>> a(n);
      ss >> a;
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      tools::triangular_array<int, std::greater<int>> a(n, 0);
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          a[i][j] = k++;
        }
      }
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      std::stringstream ss;
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          ss << k++ << " \n"[j == i - 1];
        }
      }
      tools::triangular_array<int, std::greater<int>> a(n);
      ss >> a;
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      tools::triangular_array<int, std::greater_equal<int>> a(n, 0);
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
          a[i][j] = k++;
        }
      }
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      std::stringstream ss;
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
          ss << k++ << " \n"[j == i];
        }
      }
      tools::triangular_array<int, std::greater_equal<int>> a(n);
      ss >> a;
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
  }

  return 0;
}

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

#include <functional>
#include <iostream>
#include <sstream>
#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/triangular_array.hpp"



#include <algorithm>
#include <cassert>
#line 8 "tools/triangular_array.hpp"
#include <iterator>
#include <vector>
#line 1 "tools/triangular_array_compressor.hpp"



#line 6 "tools/triangular_array_compressor.hpp"
#include <utility>

namespace tools {
  template <typename Compare>
  class triangular_array_compressor;

  template <>
  class triangular_array_compressor<::std::less<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= i && i < j && j < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * (n - 1) - 1 : i * (n - 2) - 1) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n - 1) / 2);
      auto i = k / (n - 1);
      auto j = k % (n - 1);
      if (j < n - 1 - i) {
        j += i + 1;
      } else {
        i = n - 1 - i;
        ++j;
      }
      return {i, j};
    }
  };

  template <>
  class triangular_array_compressor<::std::less_equal<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= i && i <= j && j < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * (n + 1) + 1 : i * n) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n + 1) / 2);
      auto i = k / (n + 1);
      auto j = k % (n + 1);
      if (j < n - i) {
        j += i;
      } else {
        i = n - 1 - i;
        --j;
      }
      return {i, j};
    }
  };

  template <>
  class triangular_array_compressor<::std::greater<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= j && j < i && i < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * n : i * (n - 1)) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n - 1) / 2);
      auto i = k / (n - 1);
      auto j = k % (n - 1);
      if (i <= j) {
        j -= i;
        i = n - 1 - i;
      }
      return {i, j};
    }
  };

  template <>
  class triangular_array_compressor<::std::greater_equal<int>> {
    int m_size;

  public:
    triangular_array_compressor() = default;
    triangular_array_compressor(const int n) : m_size(n) {
      assert(n >= 0);
    }

    int size() const {
      return m_size;
    }

    int compress(const int i, const int j) const {
      const auto& n = this->m_size;
      assert(0 <= j && j <= i && i < n);
      return (i >= (n + 1) / 2 ? (n - 1 - i) * (n + 1) + n - i : i * (n + 1)) + j;
    }

    ::std::pair<int, int> decompress(const int k) const {
      const auto& n = this->m_size;
      assert(0 <= k && k < n * (n + 1) / 2);
      auto i = k / (n + 1);
      auto j = k % (n + 1);
      if (i + 1 <= j) {
        j -= i + 1;
        i = n - 1 - i;
      }
      return {i, j};
    }
  };
}


#line 11 "tools/triangular_array.hpp"

namespace tools {
  template <typename T, typename Compare>
  class triangular_array;

  template <typename T>
  class triangular_array<T, ::std::less<int>> {
    ::tools::triangular_array_compressor<::std::less<int>> m_comp;
    ::std::vector<T> m_data;
  
  public:
    triangular_array() = default;
    triangular_array(const int n) : m_comp(n), m_data(n * (n - 1) / 2) {
      assert(n >= 0);
    }
    triangular_array(const int n, const T& value) : m_comp(n), m_data(n * (n - 1) / 2, value) {
      assert(n >= 0);
    }

    int size() const {
      return this->m_comp.size();
    }

    ::std::vector<T>::iterator operator[](const int i) {
      assert(0 <= i && i + 1 < this->size());
      return ::std::next(this->m_data.begin(), this->m_comp.compress(i, i + 1) - (i + 1));
    }
    ::std::vector<T>::const_iterator operator[](const int i) const {
      assert(0 <= i && i + 1 < this->size());
      return ::std::next(this->m_data.begin(), this->m_comp.compress(i, i + 1) - (i + 1));
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::triangular_array<T, ::std::less<int>>& self) {
      for (int i = 0; i + 1 < self.size(); ++i) {
        ::std::copy_n(::std::istream_iterator<T>(is), self.size() - 1 - i, ::std::next(self.m_data.begin(), self.m_comp.compress(i, i + 1)));
      }
      return is;
    }
  };

  template <typename T>
  class triangular_array<T, ::std::less_equal<int>> {
    ::tools::triangular_array_compressor<::std::less_equal<int>> m_comp;
    ::std::vector<T> m_data;
  
  public:
    triangular_array() = default;
    triangular_array(const int n) : m_comp(n), m_data(n * (n + 1) / 2) {
      assert(n >= 0);
    }
    triangular_array(const int n, const T& value) : m_comp(n), m_data(n * (n + 1) / 2, value) {
      assert(n >= 0);
    }

    int size() const {
      return this->m_comp.size();
    }

    ::std::vector<T>::iterator operator[](const int i) {
      assert(0 <= i && i < this->size());
      return ::std::next(this->m_data.begin(), this->m_comp.compress(i, i) - i);
    }
    ::std::vector<T>::const_iterator operator[](const int i) const {
      assert(0 <= i && i < this->size());
      return ::std::next(this->m_data.begin(), this->m_comp.compress(i, i) - i);
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::triangular_array<T, ::std::less_equal<int>>& self) {
      for (int i = 0; i < self.size(); ++i) {
        ::std::copy_n(::std::istream_iterator<T>(is), self.size() - i, ::std::next(self.m_data.begin(), self.m_comp.compress(i, i)));
      }
      return is;
    }
  };

  template <typename T>
  class triangular_array<T, ::std::greater<int>> {
    ::tools::triangular_array_compressor<::std::greater<int>> m_comp;
    ::std::vector<T> m_data;
  
  public:
    triangular_array() = default;
    triangular_array(const int n) : m_comp(n), m_data(n * (n - 1) / 2) {
      assert(n >= 0);
    }
    triangular_array(const int n, const T& value) : m_comp(n), m_data(n * (n - 1) / 2, value) {
      assert(n >= 0);
    }

    int size() const {
      return this->m_comp.size();
    }

    ::std::vector<T>::iterator operator[](const int i) {
      assert(1 <= i && i < this->size());
      return ::std::next(this->m_data.begin(), this->m_comp.compress(i, 0));
    }
    ::std::vector<T>::const_iterator operator[](const int i) const {
      assert(1 <= i && i < this->size());
      return ::std::next(this->m_data.begin(), this->m_comp.compress(i, 0));
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::triangular_array<T, ::std::greater<int>>& self) {
      for (int i = 1; i < self.size(); ++i) {
        ::std::copy_n(::std::istream_iterator<T>(is), i, self[i]);
      }
      return is;
    }
  };

  template <typename T>
  class triangular_array<T, ::std::greater_equal<int>> {
    ::tools::triangular_array_compressor<::std::greater_equal<int>> m_comp;
    ::std::vector<T> m_data;
  
  public:
    triangular_array() = default;
    triangular_array(const int n) : m_comp(n), m_data(n * (n + 1) / 2) {
      assert(n >= 0);
    }
    triangular_array(const int n, const T& value) : m_comp(n), m_data(n * (n + 1) / 2, value) {
      assert(n >= 0);
    }

    int size() const {
      return this->m_comp.size();
    }

    ::std::vector<T>::iterator operator[](const int i) {
      assert(0 <= i && i < this->size());
      return ::std::next(this->m_data.begin(), this->m_comp.compress(i, 0));
    }
    ::std::vector<T>::const_iterator operator[](const int i) const {
      assert(0 <= i && i < this->size());
      return ::std::next(this->m_data.begin(), this->m_comp.compress(i, 0));
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::triangular_array<T, ::std::greater_equal<int>>& self) {
      for (int i = 0; i < self.size(); ++i) {
        ::std::copy_n(::std::istream_iterator<T>(is), i + 1, self[i]);
      }
      return is;
    }
  };
}


#line 8 "tests/triangular_array.test.cpp"

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

  for (int n = 0; n <= 7; ++n) {
    {
      tools::triangular_array<int, std::less<int>> a(n, 0);
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          a[i][j] = k++;
        }
      }
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      std::stringstream ss;
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          ss << k++ << " \n"[j == n - 1];
        }
      }
      tools::triangular_array<int, std::less<int>> a(n);
      ss >> a;
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      tools::triangular_array<int, std::less_equal<int>> a(n, 0);
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
          a[i][j] = k++;
        }
      }
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      std::stringstream ss;
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
          ss << k++ << " \n"[j == n - 1];
        }
      }
      tools::triangular_array<int, std::less_equal<int>> a(n);
      ss >> a;
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      tools::triangular_array<int, std::greater<int>> a(n, 0);
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          a[i][j] = k++;
        }
      }
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      std::stringstream ss;
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          ss << k++ << " \n"[j == i - 1];
        }
      }
      tools::triangular_array<int, std::greater<int>> a(n);
      ss >> a;
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      tools::triangular_array<int, std::greater_equal<int>> a(n, 0);
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
          a[i][j] = k++;
        }
      }
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
    {
      std::stringstream ss;
      int k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
          ss << k++ << " \n"[j == i];
        }
      }
      tools::triangular_array<int, std::greater_equal<int>> a(n);
      ss >> a;
      k = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
          assert_that(a[i][j] == k++);
        }
      }
    }
  }

  return 0;
}
Back to top page