結果

問題 No.2727 Tetrahedron Game
コンテスト
ユーザー risujiroh
提出日時 2024-04-12 22:51:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 4,729 bytes
コンパイル時間 3,006 ms
コンパイル使用メモリ 264,724 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-02 23:38:46
合計ジャッジ時間 3,693 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

namespace {

using P = kactl::Point3D<i64>;

void solve() {
  int n, k;
  scan(n, k);
  std::array<P, 4> p;
  for (const int i : rep1(3)) {
    scan(p[i].x, p[i].y, p[i].z);
  }
  std::vector<int> a(n);
  scan(a);
  std::string s;
  scan(s);
  std::vector<int> f(606);
  for (const int i : rep(101)) {
    f[i * 6] = k <= i ? 1 : 2;
  }
  for (const int i : rep(n) | views::reverse) {
    ++a[i];
    std::vector<int> nf(606);
    if (s[i] == 'K') {
      for (const int x : rep(606)) {
        if (f[x] == 2 && f[(x * a[i]) % 606] == 2) {
          nf[x] = 2;
        } else if (f[x] == 1 || f[(x * a[i]) % 606] == 1) {
          nf[x] = 1;
        }
      }
    } else {
      for (const int x : rep(606)) {
        if (f[x] == 1 && f[(x * a[i]) % 606] == 1) {
          nf[x] = 1;
        } else if (f[x] == 2 || f[(x * a[i]) % 606] == 2) {
          nf[x] = 2;
        }
      }
    }
    f = std::move(nf);
  }
  const i64 t = std::abs(p[1].cross(p[2]).dot(p[3]));
  print("DKP"[t == 0 ? 0 : f[t % 606]]);
}

}  // namespace

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::setprecision(DBL_DECIMAL_DIG);

  int t;
  scan(t);
  while (t--) {
    solve();
  }
}

#else  // __INCLUDE_LEVEL__

#include <bits/stdc++.h>

// https://github.com/kth-competitive-programming/kactl
namespace kactl {

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <class T>
struct Point3D {
  typedef Point3D P;
  typedef const P& R;
  T x, y, z;
  explicit Point3D(T x = 0, T y = 0, T z = 0) : x(x), y(y), z(z) {}
  bool operator<(R p) const { return tie(x, y, z) < tie(p.x, p.y, p.z); }
  bool operator==(R p) const { return tie(x, y, z) == tie(p.x, p.y, p.z); }
  P operator+(R p) const { return P(x + p.x, y + p.y, z + p.z); }
  P operator-(R p) const { return P(x - p.x, y - p.y, z - p.z); }
  P operator*(T d) const { return P(x * d, y * d, z * d); }
  P operator/(T d) const { return P(x / d, y / d, z / d); }
  T dot(R p) const { return x * p.x + y * p.y + z * p.z; }
  P cross(R p) const { return P(y * p.z - z * p.y, z * p.x - x * p.z, x * p.y - y * p.x); }
  T dist2() const { return x * x + y * y + z * z; }
  double dist() const { return sqrt((double)dist2()); }
  double phi() const { return atan2(y, x); }
  double theta() const { return atan2(sqrt(x * x + y * y), z); }
  P unit() const { return *this / (T)dist(); }
  P normal(P p) const { return cross(p).unit(); }
  P rotate(double angle, P axis) const {
    double s = sin(angle), c = cos(angle);
    P u = axis.unit();
    return u * dot(u) * (1 - c) + (*this) * c - cross(u) * s;
  }
};

}  // namespace kactl

template <class T, class U = T>
bool chmin(T& x, U&& y) {
  return y < x && (x = std::forward<U>(y), true);
}

template <class T, class U = T>
bool chmax(T& x, U&& y) {
  return x < y && (x = std::forward<U>(y), true);
}

template <std::signed_integral T = int>
T inf() {
  T ret;
  std::memset(&ret, 0x3f, sizeof(ret));
  return ret;
}

template <std::floating_point T>
T inf() {
  return std::numeric_limits<T>::infinity();
}

template <class T>
concept Range = std::ranges::range<T> && !std::convertible_to<T, std::string_view>;

template <class T>
concept Tuple = std::__is_tuple_like<T>::value && !Range<T>;

namespace std {

istream& operator>>(istream& is, Range auto&& r) {
  for (auto&& e : r) {
    is >> e;
  }
  return is;
}

istream& operator>>(istream& is, Tuple auto&& t) {
  return apply([&](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);
}

ostream& operator<<(ostream& os, Range auto&& r) {
  for (string_view sep = ""; auto&& e : r) {
    os << exchange(sep, " ") << e;
  }
  return os;
}

ostream& operator<<(ostream& os, Tuple auto&& t) {
  const auto f = [&](auto&... xs) -> ostream& {
    [[maybe_unused]] string_view sep = "";
    ((os << exchange(sep, " ") << xs), ...);
    return os;
  };
  return apply(f, t);
}

}  // namespace std

void scan(auto&&... xs) { std::cin >> std::tie(xs...); }
void print(auto&&... xs) { std::cout << std::tie(xs...) << '\n'; }

template <class F>
class fix {
 public:
  explicit fix(F f) : f_(std::move(f)) {}

  decltype(auto) operator()(auto&&... xs) const {
    return f_(std::ref(*this), std::forward<decltype(xs)>(xs)...);
  }

 private:
  F f_;
};

inline auto rep(int l, int r) { return std::views::iota(std::min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }

using namespace std::literals;

namespace ranges = std::ranges;
namespace views = std::views;

using i64 = std::int64_t;

#endif  // __INCLUDE_LEVEL__
0