結果
問題 | No.973 余興 |
ユーザー | yakamoto |
提出日時 | 2020-01-18 14:19:41 |
言語 | Kotlin (1.9.23) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,969 bytes |
コンパイル時間 | 18,089 ms |
コンパイル使用メモリ | 434,872 KB |
実行使用メモリ | 130,996 KB |
最終ジャッジ日時 | 2023-09-09 21:56:50 |
合計ジャッジ時間 | 93,608 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,675 ms
128,904 KB |
testcase_01 | AC | 2,678 ms
129,076 KB |
testcase_02 | AC | 3,057 ms
128,880 KB |
testcase_03 | AC | 2,738 ms
128,924 KB |
testcase_04 | AC | 3,034 ms
129,092 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 2,466 ms
128,912 KB |
testcase_11 | AC | 1,577 ms
75,780 KB |
testcase_12 | AC | 1,603 ms
75,336 KB |
testcase_13 | WA | - |
testcase_14 | AC | 1,545 ms
75,356 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 430 ms
56,476 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 454 ms
56,488 KB |
testcase_23 | AC | 443 ms
56,600 KB |
testcase_24 | AC | 445 ms
56,444 KB |
testcase_25 | AC | 413 ms
55,700 KB |
testcase_26 | AC | 427 ms
56,452 KB |
testcase_27 | AC | 446 ms
56,572 KB |
testcase_28 | WA | - |
testcase_29 | AC | 451 ms
56,512 KB |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | TLE | - |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | TLE | - |
testcase_40 | AC | 306 ms
52,956 KB |
testcase_41 | AC | 298 ms
52,892 KB |
testcase_42 | AC | 293 ms
53,064 KB |
testcase_43 | WA | - |
testcase_44 | AC | 297 ms
53,008 KB |
testcase_45 | WA | - |
testcase_46 | AC | 3,491 ms
129,932 KB |
testcase_47 | WA | - |
testcase_48 | AC | 3,508 ms
130,104 KB |
testcase_49 | WA | - |
testcase_50 | AC | 3,445 ms
129,840 KB |
testcase_51 | WA | - |
testcase_52 | WA | - |
testcase_53 | AC | 3,634 ms
129,804 KB |
testcase_54 | AC | 3,720 ms
129,924 KB |
testcase_55 | AC | 3,633 ms
128,932 KB |
ソースコード
import kotlin.math.max import kotlin.math.min val MOD = 1_000_000_007 fun main() { val (N, X) = readInts() val A = readInts() if (N == 1) { println("B") return } val dpL = Array(N){SegmentTree(N - it, true){a, b -> a and b}} val dpR = Array(N){SegmentTree(it + 1, true){a, b -> a and b}} for (i in 0 until N) { // 1個だけ残ってる場合はlose dpL[i].update(0, false) dpR[i].update(0, false) } val mxR = run { val res = IntArray(N) var sum = 0L var r = N - 1 for (l in N - 1 downTo 0) { sum += A[l] while (r > l && sum > X) { sum -= A[r] r-- } res[l] = r - l + 1 } res } debug(mxR) val mxL = run { val res = IntArray(N) var sum = 0L var l = 0 for (r in 0 until N) { sum += A[r] while (l < r && sum > X) { sum -= A[l] l++ } res[r] = r - l + 1 } res } debug(mxL) for (len in 2 until N + 1) { for (l in 0 until N - len) { val r = l + len - 1 val win = !dpL[l].query(max(0, len-1-mxL[r]), len-1) or !dpR[r].query(max(0, len-1-mxR[l]), len-1) dpL[l].update(len - 1, win) dpR[r].update(len - 1, win) } } if (dpL[0].query(N-1, N)) println("A") else println("B") } class SegmentTree(n: Int, val zero: Boolean, val f: (Boolean, Boolean) -> Boolean) { private val N = if (Integer.highestOneBit(n) == n) n else Integer.highestOneBit(n) shl 1 private val dat = BooleanArray(2 * N){zero} fun update(i: Int, a: Boolean) { var ix = i + N dat[ix] = a while(ix > 1) { dat[ix shr 1] = f(dat[ix], dat[ix xor 1]) ix = ix shr 1 } } /** * [a, b) */ fun query(a: Int, b: Int): Boolean { var res: Boolean = zero var left = a + N var right = b - 1 + N while(left <= right) { if ((left and 1) == 1) res = f(res, dat[left]) if ((right and 1) == 0) res = f(res, dat[right]) left = (left + 1) shr 1 // 右の子供なら右の親に移動 right = (right - 1) shr 1 // 左の子供なら左の親に移動 } return res } } private val isDebug = try { // なんか本番でエラーでる System.getenv("MY_DEBUG") != null } catch (t: Throwable) { false } private fun readLn() = readLine()!! private fun readStrings() = readLn().split(" ") private fun readInts() = readStrings().map { it.toInt() }.toIntArray() private fun readLongs() = readStrings().map { it.toLong() }.toLongArray() private inline fun debug(msg: () -> String) { if (isDebug) System.err.println(msg()) } private fun debug(a: LongArray) { debug{a.joinToString(" ")} } private fun debug(a: IntArray) { debug{a.joinToString(" ")} } private fun debug(a: BooleanArray) { debug{a.map{if(it) 1 else 0}.joinToString("")} } private fun debugDim(A: Array<IntArray>) { if (isDebug) { for (a in A) { debug(a) } } }