AtCoderBeginnerContest230 C問題300点 「X drawing」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 10^{18}
解法・お気持ち
操作1,操作2をマス目上に書くと以下のような状態になっています。
https://gyazo.com/973511b1145417b248e2abc0fa018932
座標$ (A, B) の対角線上にあるものです。
この対角線上にある座標を$ (y,x )としてみます。
このような対角線上にある座標の条件は$ |y-A| = |x - B|です。
よって、$ P \leq y \leq Qかつ$ R\leq j \leq Sを満たすマス$ (y, x)について、以上の条件を満たすかを調べてあげればよいです。
計算量
$ O(L)
ただし、$ L \leq 3 \times 10^5
新たな学び
反省点
コード
code: go
func main() {
io := NewIo()
defer io.Flush()
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
get64 := func() int64 {
return int64(io.NextInt())
}
_, A, B := get64(), get64(), get64()
P, Q, R, S := get64(), get64(), get64(), get64()
IsGood := func(y, x int64) bool {
dy := A - y
dx := B - x
if dy < 0 {
dy = -dy
}
if dx < 0 {
dx = -dx
}
return dy == dx
}
for y := P; y <= Q; y++ {
for x := R; x <= S; x++ {
if IsGood(y, x) {
io.Printf("#")
} else {
io.Printf(".")
}
}
io.PrintLn()
}
}