結果

問題 No.1226 I hate Robot Arms
ユーザー yakamotoyakamoto
提出日時 2020-09-12 19:20:20
言語 Kotlin
(1.9.23)
結果
TLE  
実行時間 -
コード長 7,908 bytes
コンパイル時間 21,459 ms
コンパイル使用メモリ 476,584 KB
実行使用メモリ 168,984 KB
最終ジャッジ日時 2024-06-10 18:20:28
合計ジャッジ時間 77,713 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 342 ms
58,824 KB
testcase_01 AC 337 ms
60,848 KB
testcase_02 AC 1,548 ms
115,864 KB
testcase_03 AC 1,590 ms
118,352 KB
testcase_04 AC 1,594 ms
153,768 KB
testcase_05 AC 1,687 ms
159,356 KB
testcase_06 TLE -
testcase_07 AC 1,420 ms
112,240 KB
testcase_08 AC 1,075 ms
153,124 KB
testcase_09 TLE -
testcase_10 AC 889 ms
102,140 KB
testcase_11 AC 1,831 ms
156,976 KB
testcase_12 AC 1,299 ms
125,016 KB
testcase_13 AC 1,356 ms
157,308 KB
testcase_14 TLE -
testcase_15 AC 908 ms
151,512 KB
testcase_16 TLE -
testcase_17 AC 1,422 ms
118,440 KB
testcase_18 AC 1,131 ms
112,084 KB
testcase_19 AC 1,798 ms
154,472 KB
testcase_20 AC 1,714 ms
154,500 KB
testcase_21 AC 1,995 ms
157,288 KB
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:12:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
  private inline fun vec(x: Double, y: Double) =
          ^
Main.kt:18:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
  private inline fun I(n: Int) =
          ^
Main.kt:25:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
  private inline fun reset(m: Mat) {
          ^
Main.kt:33:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
  private inline fun resetI(m: Mat) {
          ^
Main.kt:46:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
  private inline fun mulMat(a: Mat, b: Mat, c: Mat) {
          ^
Main.kt:68:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
  private inline fun plusMat(a: Mat, b: Mat) {
          ^
Main.kt:100:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
    private inline fun applyOperation(k: Int, x: Mat) {
            ^
Main.kt:106:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
    private inline fun push(k: Int) {
            ^
Main.kt:183:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
  private inline fun rotate(d: Int): Mat {
          ^
Main.kt:191:11: warning: expected performance impact from inlining is insignificant. Inlining works best

ソースコード

diff # 

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 vec(x: Double, y: Double) =
    arrayOf(
      doubleArrayOf(x),
      doubleArrayOf(y)
    )

  private inline fun I(n: Int) =
    Array(n) {
      val res = DoubleArray(n)
      res[it] = 1.0
      res
    }

  private inline fun reset(m: Mat) {
    for (i in m.indices) {
      for (j in m[0].indices) {
        m[i][j] = 0.0
      }
    }
  }

  private inline fun resetI(m: Mat) {
    for (i in m.indices) {
      for (j in m.indices) {
        m[i][j] = if (i == j) 1.0 else 0.0
      }
    }
  }

  private val tmp = I(2)
  /**
   * c = a * b
   * 計算途中でaを書き換えるかもしれないのでtmpに一旦移す
   */
  private inline fun mulMat(a: Mat, b: Mat, c: Mat) {
    val n = a.indices
    val m = b[0].indices
    for (i in n) {
      for (j in m) {
        var v = 0.0
        for (k in a[0].indices) {
          v += a[i][k] * b[k][j]
        }
        tmp[i][j] = v
      }
    }
    for (i in n) {
      for (j in m) {
        c[i][j] = tmp[i][j]
      }
    }
  }

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


  /**
   * 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) {
        plusMat(value[i], value[i*2])
        plusMat(value[i], value[i*2 + 1])
      }
    }

    private inline fun applyOperation(k: Int, x: Mat) {
      mulMat(x, value[k], value[k]) // valueはvectorなので MVの形になるように計算する
      mulMat(x, delay[k], 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])
        resetI(delay[k])
        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)
      reset(value[k])
      plusMat(value[k], value[lft])
      plusMat(value[k], value[rgt])
    }

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

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

      query(a, b, dest, lft, l, m)
      query(a, b, dest, 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(0.0, 0.0)
    vec.query(0, i + 1, mat)
    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("inspec($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()
}
0