結果

問題 No.873 バイナリ、ヤバいなり！ｗ
ユーザー yakamotoyakamoto
提出日時 2019-08-31 22:23:09
言語 Kotlin
(1.9.23)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 378 ms
60,236 KB
testcase_02 AC 531 ms
62,224 KB
testcase_03 AC 495 ms
62,368 KB
testcase_04 AC 313 ms
60,344 KB
testcase_05 AC 298 ms
56,840 KB
testcase_06 AC 297 ms
56,716 KB
testcase_07 AC 313 ms
60,172 KB
testcase_08 AC 369 ms
60,388 KB
testcase_09 AC 316 ms
60,260 KB
testcase_10 AC 319 ms
60,336 KB
testcase_11 AC 302 ms
56,836 KB
testcase_12 AC 318 ms
56,908 KB
testcase_13 AC 314 ms
60,224 KB
testcase_14 AC 312 ms
60,196 KB
testcase_15 AC 317 ms
60,224 KB
testcase_16 AC 304 ms
56,848 KB
testcase_17 AC 311 ms
60,208 KB
testcase_18 AC 319 ms
60,136 KB
testcase_19 AC 314 ms
60,140 KB
testcase_20 AC 302 ms
56,804 KB
testcase_21 AC 311 ms
60,080 KB
testcase_22 AC 314 ms
60,104 KB
testcase_23 AC 299 ms
56,884 KB
testcase_24 AC 302 ms
56,596 KB
testcase_25 AC 312 ms
60,256 KB
testcase_26 AC 310 ms
60,048 KB
testcase_27 AC 313 ms
60,232 KB
testcase_28 AC 317 ms
60,248 KB
testcase_29 AC 313 ms
60,168 KB
testcase_30 AC 308 ms
60,208 KB
testcase_31 AC 321 ms
60,292 KB
testcase_32 AC 330 ms
60,292 KB
testcase_33 AC 314 ms
56,864 KB
testcase_34 AC 351 ms
60,056 KB
testcase_35 AC 533 ms
62,276 KB
testcase_36 AC 436 ms
62,240 KB
testcase_37 AC 542 ms
62,476 KB
testcase_38 AC 537 ms
62,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// なんか本番でエラーでる
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