結果
| 問題 | No.675 ドットちゃんたち |
| コンテスト | |
| ユーザー |
 ooaiu
|
| 提出日時 | 2026-06-13 14:38:23 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 80 ms / 2,000 ms |
| コード長 | 10,428 bytes |
| 記録 | |
| コンパイル時間 | 2,792 ms |
| コンパイル使用メモリ | 356,396 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-06-13 14:38:29 |
| 合計ジャッジ時間 | 5,440 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_1 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 8 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
template <class F> class y_combinator {
F f;
public:
y_combinator(F&& f) : f(std::forward<F>(f)) {}
template <class... Args> auto operator()(Args&&... args) const { return f(*this, std::forward<Args>(args)...); }
};
constexpr int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vc<T>>;
template <class T, class U = std::less<T>> using prique = priority_queue<T, vector<T>, U>;
#define overload(a, b, c, d, e, ...) e
#define len(x) (ll)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep1(n) for (ll _ = 0; _ < ll(n); _++)
#define rep2(i, n) for (ll i = 0; i < ll(n); i++)
#define rep3(i, a, b) for (ll i = ll(a); i < ll(b); i++)
#define rep4(i, a, b, c) for (ll i = ll(a); i < ll(b); i += ll(c))
#define rep(...) overload(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(i, n) for (ll i = ll(n) - 1; i >= 0; i--)
template <class T> void dedup(vector<T>& a) { sort(all(a)), a.erase(unique(all(a)), a.end()); }
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
namespace cppio {
template <typename T> struct is_tuple_like : false_type {};
template <typename... Ts> struct is_tuple_like<tuple<Ts...>> : true_type {};
template <typename T, typename U> struct is_tuple_like<pair<T, U>> : true_type {};
template <typename T, typename = void> struct is_container : false_type {};
template <typename T> struct is_container<T, void_t<decltype(begin(declval<T&>()))>> : bool_constant<!is_same_v<decay_t<T>, string> && !is_same_v<decay_t<T>, char*> && !is_same_v<decay_t<T>, const char*> && !is_array_v<remove_reference_t<T>>> {};
template <typename T> void _in(T& x) {
if constexpr (is_tuple_like<T>::value) apply([](auto&... elems) { (_in(elems), ...); }, x);
else if constexpr (is_container<T>::value) {
for (auto& e : x) _in(e);
} else cin >> x;
}
template <typename... Ts> void _in_all(Ts&... args) { (_in(args), ...); }
template <typename T> void _out(const T& x) {
bool first = true;
if constexpr (is_tuple_like<T>::value) {
apply([&](const auto&... elems) { ((cout << (first ? "" : " "), _out(elems), first = false), ...); }, x);
} else if constexpr (is_container<T>::value) {
for (const auto& e : x) {
if (!first) cout << ' ';
_out(e), first = false;
}
} else cout << x;
}
template <typename... Ts> void _print(const Ts&... args) {
bool first = true;
((cout << (first ? "" : " "), _out(args), first = false), ...);
}
template <typename... Ts> void _out_all(const Ts&... args) { _print(args...), cout << '\n'; }
template <typename... Ts> void _out_no_el(const Ts&... args) { _print(args...); }
} // namespace cppio
#define IN(...) cppio::_in_all(__VA_ARGS__)
#define OUT(...) cppio::_out_all(__VA_ARGS__)
#define out(...) cppio::_out_no_el(__VA_ARGS__)
#define INT(...) int __VA_ARGS__; IN(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; IN(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; IN(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; IN(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); IN(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); IN(name)
#define RETURN(...) do { __VA_ARGS__; return; } while (0)
bool Yes(bool b = true) { OUT(b ? "Yes" : "No"); return b; }
bool No(bool b = true) { Yes(!b); return b; }
bool YES(bool b = true) { OUT(b ? "YES" : "NO"); return b; }
bool NO(bool b = true) { YES(!b); return b; }
#ifdef ONLINE_JUDGE
#define debug(...) (void(0))
#endif
#include <atcoder/modint>
using mint = atcoder::modint1000000007;
template <class T> struct Matrix {
private:
int H, W;
vector<vector<T>> dat;
public:
Matrix() : H(0), W(0) {}
Matrix(int h, int w, const T& v = T{}) : H(h), W(w), dat(h, vector<T>(w, v)) {}
Matrix(const vector<vector<T>>& v)
: H((int)v.size()), W(v.empty() ? 0 : (int)v[0].size()), dat(v) {}
Matrix(vector<vector<T>>&& v)
: H((int)v.size()), W(v.empty() ? 0 : (int)v[0].size()), dat(move(v)) {}
static Matrix eye(int sz) {
Matrix res(sz, sz);
for (int i = 0; i < sz; i++) res[i][i] = T{1};
return res;
}
static Matrix col_vector(const vector<T>& v) {
Matrix res((int)v.size(), 1);
for (int i = 0; i < (int)v.size(); i++) res[i][0] = v[i];
return res;
}
static Matrix row_vector(const vector<T>& v) {
Matrix res(1, (int)v.size());
for (int j = 0; j < (int)v.size(); j++) res[0][j] = v[j];
return res;
}
int height() const { return H; }
int width() const { return W; }
bool is_square() const { return H == W; }
vector<T>& operator[](int i) { return dat[i]; }
const vector<T>& operator[](int i) const { return dat[i]; }
Matrix& operator+=(const Matrix& o) {
assert(H == o.H && W == o.W);
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) dat[i][j] += o[i][j];
return *this;
}
Matrix& operator-=(const Matrix& o) {
assert(H == o.H && W == o.W);
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) dat[i][j] -= o[i][j];
return *this;
}
Matrix& operator*=(const Matrix& o) {
assert(W == o.H);
Matrix res(H, o.W);
for (int i = 0; i < H; i++)
for (int k = 0; k < W; k++)
for (int j = 0; j < o.W; j++)
res[i][j] += dat[i][k] * o[k][j];
return *this = move(res);
}
Matrix& operator*=(const T& s) {
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) dat[i][j] *= s;
return *this;
}
Matrix operator-() const {
Matrix res(H, W);
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) res[i][j] = -dat[i][j];
return res;
}
friend Matrix operator+(Matrix lhs, const Matrix& rhs) { return lhs += rhs; }
friend Matrix operator-(Matrix lhs, const Matrix& rhs) { return lhs -= rhs; }
friend Matrix operator*(Matrix lhs, const Matrix& rhs) { return lhs *= rhs; }
friend Matrix operator*(Matrix lhs, const T& rhs) { return lhs *= rhs; }
friend Matrix operator*(const T& lhs, Matrix rhs) { return rhs *= lhs; }
bool operator==(const Matrix& o) const { return H == o.H && W == o.W && dat == o.dat; }
bool operator!=(const Matrix& o) const { return !(*this == o); }
Matrix pow(long long b) const {
assert(is_square());
assert(b >= 0);
Matrix a = *this, res = eye(H);
for (; b > 0; b >>= 1) {
if (b & 1) res *= a;
a *= a;
}
return res;
}
Matrix transpose() const {
Matrix res(W, H);
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) res[j][i] = dat[i][j];
return res;
}
};
template <class T> struct ColVector {
private:
int N;
vector<T> dat;
public:
ColVector() : N(0) {}
ColVector(int n, const T& v = T{}) : N(n), dat(n, v) {}
ColVector(const vector<T>& v) : N((int)v.size()), dat(v) {}
ColVector(vector<T>&& v) : N((int)v.size()), dat(move(v)) {}
int size() const { return N; }
T& operator[](int i) { return dat[i]; }
const T& operator[](int i) const { return dat[i]; }
vector<T>& data() { return dat; }
const vector<T>& data() const { return dat; }
ColVector& operator+=(const ColVector& o) {
assert(N == o.N);
for (int i = 0; i < N; i++) dat[i] += o[i];
return *this;
}
ColVector& operator-=(const ColVector& o) {
assert(N == o.N);
for (int i = 0; i < N; i++) dat[i] -= o[i];
return *this;
}
ColVector& operator*=(const T& s) {
for (int i = 0; i < N; i++) dat[i] *= s;
return *this;
}
ColVector operator-() const {
ColVector res(N);
for (int i = 0; i < N; i++) res[i] = -dat[i];
return res;
}
friend ColVector operator+(ColVector lhs, const ColVector& rhs) { return lhs += rhs; }
friend ColVector operator-(ColVector lhs, const ColVector& rhs) { return lhs -= rhs; }
friend ColVector operator*(ColVector lhs, const T& rhs) { return lhs *= rhs; }
friend ColVector operator*(const T& lhs, ColVector rhs) { return rhs *= lhs; }
bool operator==(const ColVector& o) const { return N == o.N && dat == o.dat; }
bool operator!=(const ColVector& o) const { return !(*this == o); }
friend ColVector operator*(const Matrix<T>& A, const ColVector& v) {
assert(A.width() == v.N);
ColVector res(A.height());
for (int i = 0; i < A.height(); i++)
for (int k = 0; k < v.N; k++)
res[i] += A[i][k] * v[k];
return res;
}
};
using D = Matrix<ll>;
D mk(ll x, ll y) {
vector<vector<ll>> t = {
{1, 0, x},
{0, 1, y},
{0, 0, 1}};
return D(t);
}
void run_case() {
vector<vector<ll>> A = {
{0, 1, 0},
{-1, 0, 0},
{0, 0, 1},
};
vector<vector<ll>> B = {
{0, -1, 0},
{1, 0, 0},
{0, 0, 1},
};
D MA = A;
D MB = B;
LL(N, Px, Py);
D P = D::eye(3);
vector<int> T(N), delta(N);
rep(i, N) {
IN(T[i]);
if (T[i] != 3) IN(delta[i]);
if (T[i] == 1) {
P = mk(delta[i], 0) * P;
} else if (T[i] == 2) {
P = mk(0, delta[i]) * P;
} else {
P = MA * P;
}
}
rep(i, N) {
ColVector<ll> c({Px, Py, 1});
auto nc = P * c;
OUT(nc[0], nc[1]);
if (T[i] == 1) {
P *= mk(-delta[i], 0);
} else if (T[i] == 2) {
P *= mk(0, -delta[i]);
} else {
P *= MB;
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::fixed(std::cout).precision(16);
ll t = 1;
while (t--) run_case();
}