Submission #1546164
Source Code Expand
fun main(args: Array<String>) { val a = readLine()!!.map { it == '1' }.toBooleanArray() val b = readLine()!!.map { it == '1' }.toBooleanArray() fun f(i: Int) = (i + a.size) % a.size if (b.all { !it }) { println(if (a.all { !it }) 0 else -1) return } val left = IntArray(a.size) val right = IntArray(a.size) var t = b.size - b.lastIndexOf(true) - 1 for (i in left.indices) { left[i] = if (b[i]) 0 else t + 1 t = left[i] } t = b.indexOf(true) for (i in right.indices.reversed()) { right[i] = if (b[i]) 0 else t + 1 t = right[i] } var res = a.size * 5 for (sh in -a.size..a.size) { val flip = a.indices .filter { a[it] != b[f(it + sh)] } .map { Pair( Math.min(left[it], Math.max(left[it] + sh, 0)), Math.min(right[it], Math.max(right[it] - sh, 0)) ) } .toTypedArray() .sortedBy { -it.first } var shifts = 0 if (!flip.isEmpty()) { shifts = flip[0].first var tRight = flip[0].second for ((pLeft, pRight) in flip.drop(1)) { shifts = Math.min(shifts, tRight + pLeft) tRight = Math.max(tRight, pRight) } shifts = Math.min(shifts, tRight) } res = Math.min(res, shifts * 2 + flip.size + Math.abs(sh)) } println(res) }
Submission Info
Submission Time | |
---|---|
Task | D - Shift and Flip |
User | AlexeyEnkov |
Language | Kotlin (1.0.0) |
Score | 1000 |
Code Size | 1570 Byte |
Status | AC |
Exec Time | 1678 ms |
Memory | 122504 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 1000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 235 ms | 34420 KB |
sample_02.txt | AC | 207 ms | 29684 KB |
sample_03.txt | AC | 236 ms | 36084 KB |
sample_04.txt | AC | 235 ms | 34396 KB |
subtask_1_01.txt | AC | 207 ms | 31780 KB |
subtask_1_02.txt | AC | 232 ms | 36268 KB |
subtask_1_03.txt | AC | 233 ms | 36260 KB |
subtask_1_04.txt | AC | 211 ms | 29748 KB |
subtask_1_05.txt | AC | 816 ms | 116748 KB |
subtask_1_06.txt | AC | 217 ms | 33528 KB |
subtask_1_07.txt | AC | 360 ms | 67900 KB |
subtask_1_08.txt | AC | 212 ms | 31744 KB |
subtask_1_09.txt | AC | 231 ms | 35852 KB |
subtask_1_10.txt | AC | 284 ms | 35164 KB |
subtask_1_11.txt | AC | 1409 ms | 112700 KB |
subtask_1_12.txt | AC | 1437 ms | 110116 KB |
subtask_1_13.txt | AC | 1425 ms | 112952 KB |
subtask_1_14.txt | AC | 757 ms | 116836 KB |
subtask_1_15.txt | AC | 1269 ms | 120708 KB |
subtask_1_16.txt | AC | 1430 ms | 121432 KB |
subtask_1_17.txt | AC | 1367 ms | 121228 KB |
subtask_1_18.txt | AC | 1468 ms | 119060 KB |
subtask_1_19.txt | AC | 1617 ms | 111020 KB |
subtask_1_20.txt | AC | 1678 ms | 112120 KB |
subtask_1_21.txt | AC | 754 ms | 119148 KB |
subtask_1_22.txt | AC | 743 ms | 116968 KB |
subtask_1_23.txt | AC | 925 ms | 119008 KB |
subtask_1_24.txt | AC | 933 ms | 119172 KB |
subtask_1_25.txt | AC | 924 ms | 118136 KB |
subtask_1_26.txt | AC | 286 ms | 36292 KB |
subtask_1_27.txt | AC | 366 ms | 42024 KB |
subtask_1_28.txt | AC | 569 ms | 46856 KB |
subtask_1_29.txt | AC | 910 ms | 69564 KB |
subtask_1_30.txt | AC | 1366 ms | 122504 KB |
subtask_1_31.txt | AC | 235 ms | 34412 KB |
subtask_1_32.txt | AC | 291 ms | 36296 KB |
subtask_1_33.txt | AC | 405 ms | 45576 KB |
subtask_1_34.txt | AC | 556 ms | 44908 KB |
subtask_1_35.txt | AC | 933 ms | 72248 KB |
subtask_1_36.txt | AC | 1485 ms | 120504 KB |
subtask_1_37.txt | AC | 292 ms | 36496 KB |
subtask_1_38.txt | AC | 380 ms | 42848 KB |
subtask_1_39.txt | AC | 613 ms | 44676 KB |
subtask_1_40.txt | AC | 968 ms | 51308 KB |
subtask_1_41.txt | AC | 1384 ms | 111148 KB |
subtask_1_42.txt | AC | 1358 ms | 110352 KB |
subtask_1_43.txt | AC | 1398 ms | 121044 KB |
subtask_1_44.txt | AC | 1477 ms | 119624 KB |
subtask_1_45.txt | AC | 1467 ms | 117956 KB |
subtask_1_46.txt | AC | 1414 ms | 120968 KB |