結果

問題 No.873 バイナリ、ヤバいなり！ｗ
ユーザー yakamotoyakamoto
提出日時 2019-08-31 22:23:09
言語 Kotlin
(1.9.23)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,639 bytes
コンパイル時間 17,484 ms
コンパイル使用メモリ 430,444 KB
実行使用メモリ 59,124 KB
最終ジャッジ日時 2023-09-06 11:59:11
合計ジャッジ時間 33,110 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 402 ms
56,784 KB
testcase_02 AC 580 ms
58,648 KB
testcase_03 AC 524 ms
59,124 KB
testcase_04 AC 293 ms
55,960 KB
testcase_05 AC 266 ms
52,776 KB
testcase_06 AC 264 ms
52,672 KB
testcase_07 AC 293 ms
56,068 KB
testcase_08 AC 330 ms
56,684 KB
testcase_09 AC 281 ms
56,220 KB
testcase_10 AC 290 ms
56,368 KB
testcase_11 AC 271 ms
52,712 KB
testcase_12 AC 291 ms
52,884 KB
testcase_13 AC 288 ms
56,184 KB
testcase_14 AC 283 ms
55,988 KB
testcase_15 AC 284 ms
55,876 KB
testcase_16 AC 288 ms
52,736 KB
testcase_17 AC 315 ms
55,968 KB
testcase_18 AC 312 ms
55,864 KB
testcase_19 AC 316 ms
56,540 KB
testcase_20 AC 289 ms
52,508 KB
testcase_21 AC 292 ms
56,032 KB
testcase_22 AC 278 ms
56,044 KB
testcase_23 AC 274 ms
52,644 KB
testcase_24 AC 264 ms
52,664 KB
testcase_25 AC 278 ms
56,032 KB
testcase_26 AC 285 ms
56,008 KB
testcase_27 AC 290 ms
56,108 KB
testcase_28 AC 278 ms
55,976 KB
testcase_29 AC 287 ms
56,012 KB
testcase_30 AC 285 ms
55,880 KB
testcase_31 AC 276 ms
55,984 KB
testcase_32 AC 298 ms
56,204 KB
testcase_33 AC 289 ms
52,864 KB
testcase_34 AC 327 ms
56,908 KB
testcase_35 AC 586 ms
58,820 KB
testcase_36 AC 470 ms
56,920 KB
testcase_37 AC 616 ms
58,876 KB
testcase_38 AC 594 ms
59,012 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