結果

問題 No.873 バイナリ、ヤバいなり！ｗ
コンテスト
ユーザー yakamoto
提出日時 2019-08-31 22:23:09
言語 Kotlin
(2.1.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,639 bytes
コンパイル時間 16,632 ms
コンパイル使用メモリ 460,788 KB
実行使用メモリ 62,476 KB
最終ジャッジ日時 2024-06-24 06:36:34
合計ジャッジ時間 31,294 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// なんか本番でエラーでる
private val isDebug = runCatching {
  System.getenv("MY_DEBUG") != null
}.fold({it}, {false})

private fun readLn() = readLine()!!
private fun readInt() = readLn().toInt()
private fun readStrings() = readLn().split(" ")
private fun readInts() = readStrings().map { it.toInt() }.toIntArray()
private fun readLongs() = readStrings().map { it.toLong() }.toLongArray()
private fun debug(msg: () -> String) {
  if (isDebug) System.err.println(msg())
}
private fun debug(a: IntArray) {
  if (isDebug) debug{a.joinToString(" ")}
}

val MOD = 1000000007

data class Entry(val i: Int, val x: Long)

fun main() {
  val N = readInt()
  val dp = IntArray(N + 1){1e9.toInt()}
  dp[0] = 0
  val lst = IntArray(N + 1)
  for (i in 1..N) {
    var j = 1
    while(i - j * j >= 0) {
      if (dp[i] > dp[i - j * j] + j) {
        dp[i] = dp[i - j * j] + j
        lst[i] = j
      }
      j++
    }
  }

  debug(dp)
  debug(lst)

  val rt = mutableListOf<Int>()
  var i = N
  while(i > 0) {
    rt.add(lst[i])
    i -= lst[i] * lst[i]
  }

  debug{rt.joinToString(" ")}
  val odds = rt.filter { it % 2 == 1 }.sorted()
  val evens = rt.filter { it % 2 == 0 }.sorted().toMutableList()

  val ans = StringBuffer()
  var cur = 0
  fun add(cnt: Int) {
    repeat(cnt) {
      ans.append(cur)
      cur = cur xor 1
    }
    cur = cur xor 1
  }

  for (x in odds) {
    add(x)
  }
  while(evens.isNotEmpty()) {
    if (cur == 0) {
      val x = evens.last()
      evens.removeAt(evens.size - 1)
      add(x)
    } else {
      val x = evens.first()
      evens.removeAt(0)
      add(x)
    }
  }
  println(ans.toString())
}
0