comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: test/aoj/1181.test.cpp

Depends on

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/1181

#include "src/cpp-template/header/change-max.hpp"
#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/cpp-template/header/vector-ios.hpp"
#include "src/utility/class/dice.hpp"

#include <iostream>
#include <map>
#include <utility>
#include <vector>

namespace luz {

  using coordinate = std::pair< isize, isize >;
  using dice       = Dice< i32 >;
  using hs_map     = std::map< coordinate, usize >;
  using tops_map   = std::map< coordinate, i32 >;

  void put(dice &d, isize y, isize x, hs_map &hs, tops_map &tops) {
    coordinate now(y, x);

    std::vector< isize > dy({0, 0, 1, -1});
    std::vector< isize > dx({1, -1, 0, 0});
    std::vector< usize > rot_id({2, 3, 1, 0});
    usize rid = -1;
    isize ny = y, nx = x;
    i32 max_face = 3;
    for (usize id: rep(0, 4)) {
      if (hs[coordinate(y + dy[id], x + dx[id])] >= hs[now]) continue;

      if (chmax(max_face, d.face_id(id))) {
        rid = rot_id[id];
        ny  = y + dy[id];
        nx  = x + dx[id];
      }
    }

    if (max_face < 4) {
      hs[now]++;
      tops[now] = d.top() - 1;
      return;
    }

    d.rotate_by_id(rid);
    put(d, ny, nx, hs, tops);
  }

  void solve(usize n) {
    dice d(5, 2, 4, 3, 1, 6);

    std::map< coordinate, usize > hs;
    std::map< coordinate, i32 > tops;

    for ([[maybe_unused]] usize _: rep(0, n)) {
      i32 t, f;
      std::cin >> t >> f;

      d.normalize_as_top_front(t, f);
      put(d, 0, 0, hs, tops);
    }

    std::vector< usize > ans(6);
    for (auto &[_, top]: tops) {
      ans[top]++;
    }

    std::cout << ans << std::endl;
  }

  void main_() {
    usize n;
    while (std::cin >> n, n) {
      solve(n);
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "test/aoj/1181.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/1181

#line 2 "src/cpp-template/header/change-max.hpp"

namespace luz {

  template < typename T1, typename T2 >
  inline bool chmax(T1 &a, T2 b) {
    return a < b and (a = b, true);
  }

} // namespace luz
#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

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

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 2 "src/cpp-template/header/vector-ios.hpp"

#line 4 "src/cpp-template/header/vector-ios.hpp"

#include <iostream>
#include <vector>

namespace luz {

  template < typename T >
  std::ostream &operator<<(std::ostream &os,
                           const std::vector< T > vs) {
    for (usize i: rep(0, vs.size())) {
      os << vs[i] << (i + 1 != vs.size() ? " " : "");
    }
    return os;
  }

  template < typename T >
  std::istream &operator>>(std::istream &is, std::vector< T > &vs) {
    for (T &v: vs) {
      is >> v;
    }
    return is;
  }

} // namespace luz
#line 2 "src/utility/class/dice.hpp"

#line 5 "src/utility/class/dice.hpp"

#include <array>
#include <cassert>
#line 9 "src/utility/class/dice.hpp"

namespace luz {

  template < typename T >
  class Dice {
    // +x, -x, +y, -y, +z, -z
    std::vector< T > dice;

    static constexpr std::array< std::array< T, 4 >, 6 > rot{
        {{2, 5, 3, 4},
         {4, 3, 5, 2},
         {4, 1, 5, 0},
         {0, 5, 1, 4},
         {0, 3, 1, 2},
         {2, 1, 3, 0}}};

    void rotate(const std::array< T, 4 > &idxs) {
      for (usize i: rep(1, 4)) {
        std::swap(dice[idxs[i - 1]], dice[idxs[i]]);
      }
    }

    void internal_rotate(usize base, isize count) {
      if (count != 0) {
        bool neg = count < 0;
        rotate(rot[base + neg]);
        internal_rotate(base, count + (neg ? +1 : -1));
      }
    }

    isize count_minimize(isize count) {
      return (count % 4 + 5) % 4 - 1;
    }

   public:
    Dice(): dice(6) {}
    Dice(T px, T nx, T py, T ny, T pz, T nz)
        : dice({px, nx, py, ny, pz, nz}) {}

    void rotate_x(isize count) {
      internal_rotate(0, count_minimize(count));
    }
    void rotate_y(isize count) {
      internal_rotate(2, count_minimize(count));
    }
    void rotate_z(isize count) {
      internal_rotate(4, count_minimize(count));
    }

    void rotate_by_id(usize idx) {
      rotate(rot[idx]);
    }

    T &right() {
      return dice[0];
    }
    T &left() {
      return dice[1];
    }
    T &back() {
      return dice[2];
    }
    T &front() {
      return dice[3];
    }
    T &top() {
      return dice[4];
    }
    T &bottom() {
      return dice[5];
    }

    T &face_id(usize idx) {
      assert(idx < 6);
      return dice[idx];
    }

    void normalize_as_top_front(T t, T f) {
      for (usize i: rep(0, 6)) {
        if (top() == t) {
          for ([[maybe_unused]] usize _: rep(0, 4)) {
            if (front() == f) return;
            rotate_z(1);
          }
        }

        rotate_by_id(2 * (i & 1));
      }

      assert(false);
    }
  };

  template < typename T >
  std::vector< Dice< T > > dice_enumeration(Dice< T > dice) {
    std::vector< Dice< T > > result;

    for (usize i: rep(0, 6)) {
      for ([[maybe_unused]] usize _: rep(0, 4)) {
        result.emplace_back(dice);
        dice.rotate_z(1);
      }

      dice.rotate_by_id(2 * (i & 1));
    }

    return result;
  }

} // namespace luz
#line 9 "test/aoj/1181.test.cpp"

#line 11 "test/aoj/1181.test.cpp"
#include <map>
#include <utility>
#line 14 "test/aoj/1181.test.cpp"

namespace luz {

  using coordinate = std::pair< isize, isize >;
  using dice       = Dice< i32 >;
  using hs_map     = std::map< coordinate, usize >;
  using tops_map   = std::map< coordinate, i32 >;

  void put(dice &d, isize y, isize x, hs_map &hs, tops_map &tops) {
    coordinate now(y, x);

    std::vector< isize > dy({0, 0, 1, -1});
    std::vector< isize > dx({1, -1, 0, 0});
    std::vector< usize > rot_id({2, 3, 1, 0});
    usize rid = -1;
    isize ny = y, nx = x;
    i32 max_face = 3;
    for (usize id: rep(0, 4)) {
      if (hs[coordinate(y + dy[id], x + dx[id])] >= hs[now]) continue;

      if (chmax(max_face, d.face_id(id))) {
        rid = rot_id[id];
        ny  = y + dy[id];
        nx  = x + dx[id];
      }
    }

    if (max_face < 4) {
      hs[now]++;
      tops[now] = d.top() - 1;
      return;
    }

    d.rotate_by_id(rid);
    put(d, ny, nx, hs, tops);
  }

  void solve(usize n) {
    dice d(5, 2, 4, 3, 1, 6);

    std::map< coordinate, usize > hs;
    std::map< coordinate, i32 > tops;

    for ([[maybe_unused]] usize _: rep(0, n)) {
      i32 t, f;
      std::cin >> t >> f;

      d.normalize_as_top_front(t, f);
      put(d, 0, 0, hs, tops);
    }

    std::vector< usize > ans(6);
    for (auto &[_, top]: tops) {
      ans[top]++;
    }

    std::cout << ans << std::endl;
  }

  void main_() {
    usize n;
    while (std::cin >> n, n) {
      solve(n);
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page