#552557 (Kotlin) No.1226 I hate Robot Arms

• 問題: No.1226 I hate Robot Arms
• ユーザー: yakamoto
• 提出日時: 2020-09-12 19:52:19
• 言語: Kotlin (2.1.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,501 bytes
• コンパイル時間: 16,769 ms
• コンパイル使用メモリ: 502,848 KB
• 実行使用メモリ: 239,332 KB
• 最終ジャッジ日時: 2025-01-02 13:38:59
• 合計ジャッジ時間: 74,131 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 2
other	AC * 15 TLE * 13

コンパイルメッセージ

Main.kt:12:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of function types.
  private inline fun zero(n: Int, m: Int) = Array(n){ DoubleArray(m)}
          ^^^^^^
Main.kt:14:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of function types.
  private inline fun vec(x: Double, y: Double) =
          ^^^^^^
Main.kt:20:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of function types.
  private inline fun I(n: Int) = run {
          ^^^^^^
Main.kt:28:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of function types.
  private inline fun mulMat(a: Mat, b: Mat): Mat {
          ^^^^^^
Main.kt:47:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of function types.
  private inline fun plusMat(a: Mat, b: Mat): Mat {
          ^^^^^^
Main.kt:80:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of function types.
    private inline fun applyOperation(k: Int, x: Mat) {
            ^^^^^^
Main.kt:86:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of function types.
    private inline fun push(k: Int) {
            ^^^^^^
Main.kt:159:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of function types.
  private inline fun rotate(d: Int): Mat {
          ^^^^^^
Main.kt:167:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of function types.
  private inline fun enlarge(k: Double): Mat {
          ^^^^^^
Main.kt:174:11: war

ソースコード

import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.lang.AssertionError
import java.util.*
import kotlin.math.*

typealias Mat = Array<DoubleArray>

class Solver(stream: InputStream, private val out: java.io.PrintWriter) {

  private inline fun zero(n: Int, m: Int) = Array(n){ DoubleArray(m)}

  private inline fun vec(x: Double, y: Double) =
    arrayOf(
      doubleArrayOf(x),
      doubleArrayOf(y)
    )

  private inline fun I(n: Int) = run {
    val res = zero(n, n)
    for (i in 0 until n) {
      res[i][i] = 1.0
    }
    res
  }

  private inline fun mulMat(a: Mat, b: Mat): Mat {
    val n = a.size
    val m = b[0].size
    val res = zero(n, m)
    for (i in 0 until n) {
      for (j in 0 until m) {
        var v = 0.0
        for (k in a[0].indices) {
          v += a[i][k] * b[k][j]
        }
        res[i][j] = v
      }
    }
    return res
  }

  /**
   * a += b
   */
  private inline fun plusMat(a: Mat, b: Mat): Mat {
    val res = zero(a.size, a[0].size)
    for (i in a.indices) {
      for (j in a[0].indices) {
        res[i][j] = a[i][j] + b[i][j]
      }
    }
    return res
  }


  /**
   * vectorを合成、範囲のvectorにmatrixで変更を加える
   * matrixの計算は左右交換するとおかしくなるので、回転、拡大のような順序関係ない操作だけ行える
   */
  private inner class VectorDelayMergeTree(n: Int, init: Array<Mat>) {
    private val N =
      if (Integer.highestOneBit(n) == n) n
      else Integer.highestOneBit(n) shl 1

    private val value = Array(N * 2){vec(0.0, 0.0)} // vector
    private val delay = Array(N * 2){I(2)} // 遅延したmatrix演算
    private val delayOn = BooleanArray(N * 2) // delayに値があるかどうか

    init {
      for (i in 0 until n) {
        value[N + i] = init[i]
      }
      for (i in N - 1 downTo 1) {
        value[i] = plusMat(value[i*2], value[i*2 + 1])
      }
    }

    private inline fun applyOperation(k: Int, x: Mat) {
      value[k] = mulMat(x, value[k]) // valueはvectorなので MVの形になるように計算する
      delay[k] = mulMat(x, delay[k])
      delayOn[k] = true
    }

    private inline fun push(k: Int) {
      if (k < N && delayOn[k]) {
        applyOperation(k*2, delay[k])
        applyOperation(k*2 + 1, delay[k])
        delay[k] = I(2)
        delayOn[k] = false
      }
    }

    /**
     * [a, b)
     */
    fun add(a: Int, b: Int, x: Mat, k: Int = 1, l: Int = 0, r: Int = N) {
      if (a >= r || l >= b) return // ノードが範囲からはずれてる
      if (a <= l && r <= b) { // ノードが完全に範囲に含まれる
        applyOperation(k, x)
        return
      }

      push(k)
      val m = (l + r) / 2
      val lft = k * 2
      val rgt = lft + 1

      // value[k] = add(left) + add(right)
      add(a, b, x, lft, l, m)
      add(a, b, x, rgt, m, r)
      value[k] = plusMat(value[lft], value[rgt])
    }

    /**
     * [a, b)
     */
    fun query(a: Int, b: Int, k: Int = 1, l: Int = 0, r: Int = N): Mat {
      if (a >= r || l >= b) return zero(2, 1)// ノードが範囲からはずれてる
      if (a <= l && r <= b) { // ノードが完全に範囲に含まれる
        return value[k]
      }

      push(k)
      val m = (l + r) / 2
      val lft = k * 2
      val rgt = lft + 1

      return plusMat(query(a, b, lft, l, m), query(a, b, rgt, m, r))
    }

    fun eval(i: Int): Mat {
      _eval(N + i)
      return value[N + i]
    }

    fun inspect() = run { Pair(value, delay) }

    fun _eval(k: Int) {
      if (k > 1) {
        _eval(k / 2)
      }
      push(k)
    }
  }

  private val reader = BufferedReader(InputStreamReader(stream), 32768)

  private val N = ni()
  private val Q = ni()
  private val deg = IntArray(N){0}
  private val len = LongArray(N){1}
  private val vec = run {
    val init = Array(N) {vec(1.0, 0.0)}
    VectorDelayMergeTree(N, init)
  }

  private inline fun rotate(d: Int): Mat {
    val t = d *PI*2 /360
    return arrayOf(
      doubleArrayOf(cos(t), -sin(t)),
      doubleArrayOf(sin(t), cos(t))
    )
  }

  private inline fun enlarge(k: Double): Mat {
    return arrayOf(
      doubleArrayOf(k, 0.0),
      doubleArrayOf(0.0, k)
    )
  }

  private inline fun debug(msg: String, mat: Mat) = run {
    debug{msg}
    debug{mat.map{it.joinToString(" ")}.joinToString("\n")}
    debug{""}
  }

  private inline fun point(i: Int): Mat {
    val mat = vec.query(0, i + 1)
    debug("point $i", mat)
    return mat
  }

  fun solve() {
    inspect()

    for (q in 0 until Q) {
      when(ni()) {
        0 -> {
          val i = ni() - 1
          val x = ni()
          val m = rotate(x - deg[i])
          vec.add(i, N, m)

          inspect()

          deg[i] = x
        }
        1 -> {
          val i = ni() - 1
          val x = nl()
          val mat = enlarge(x.toDouble()/len[i])
          vec.add(i, i + 1, mat)

          inspect()

          len[i] = x
        }
        else -> {
          fun format(a: Double) = run{"%.9f".format(a)}

          val i = ni() - 1
          val v = point(i)
          out.println("${format(v[0][0])} ${format(v[1][0])}")
        }
      }
    }
  }

  private inline fun inspect() {
//    if (isDebug) {
//      for (i in 1 until vec.inspect().first.size) {
//        debug("inspect($i)", vec.inspect().first[i])
//      }
//    }
  }


  private val isDebug = try {
    // なんか本番でエラーでる
    System.getenv("MY_DEBUG") != null
  } catch (t: Throwable) {
    false
  }

  private var tokenizer: StringTokenizer? = null
  private fun next(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
      tokenizer = StringTokenizer(reader.readLine())
    }
    return tokenizer!!.nextToken()
  }

  private fun ni() = next().toInt()
  private fun nl() = next().toLong()
  private fun ns() = next()
  private fun na(n: Int, offset: Int = 0): IntArray {
    return IntArray(n) { ni() + offset }
  }
  private fun nal(n: Int, offset: Int = 0): LongArray {
    val res = LongArray(n)
    for (i in 0 until n) {
      res[i] = nl() + offset
    }
    return res
  }

  private fun na2(n: Int, offset: Int = 0): Array<IntArray> {
    val a  = Array(2){IntArray(n)}
    for (i in 0 until n) {
      for (e in a) {
        e[i] = ni() + offset
      }
    }
    return a
  }

  private inline fun debug(msg: () -> String) {
    if (isDebug) System.err.println(msg())
  }

  private inline fun debug(a: LongArray) {
    debug { a.joinToString(" ") }
  }

  private inline fun debug(a: IntArray) {
    debug { a.joinToString(" ") }
  }

  private inline fun debug(a: BooleanArray) {
    debug { toString(a) }
  }

  private inline fun toString(a: BooleanArray) = run{a.map { if (it) 1 else 0 }.joinToString("")}

  private inline fun debugDim(A: Array<LongArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }
  private inline fun debugDim(A: Array<IntArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }
  private inline fun debugDim(A: Array<BooleanArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }

  /**
   * 勝手にimport消されるのを防ぎたい
   */
  private fun hoge() {
    min(1, 2)
    max(1, 2)
    abs(-10)
  }

  private inline fun assert(b: Boolean) = run{if (!b) throw AssertionError()}
}

fun main() {
  val out = java.io.PrintWriter(System.out)
  Solver(System.`in`, out).solve()
  out.flush()
}