結果
| 問題 | No.133 カードゲーム |
| ユーザー |
 mikhail
|
| 提出日時 | 2020-06-07 20:44:12 |
| 言語 | Kotlin (1.9.23) |
| 結果 |
AC
|
| 実行時間 | 261 ms / 5,000 ms |
| コード長 | 18,996 bytes |
| コンパイル時間 | 25,071 ms |
| コンパイル使用メモリ | 488,960 KB |
| 実行使用メモリ | 50,276 KB |
| 最終ジャッジ日時 | 2024-06-06 07:51:22 |
| 合計ジャッジ時間 | 29,972 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 253 ms
50,080 KB |
| testcase_01 | AC | 250 ms
50,216 KB |
| testcase_02 | AC | 246 ms
49,892 KB |
| testcase_03 | AC | 256 ms
49,864 KB |
| testcase_04 | AC | 248 ms
50,252 KB |
| testcase_05 | AC | 257 ms
49,892 KB |
| testcase_06 | AC | 259 ms
50,076 KB |
| testcase_07 | AC | 258 ms
50,276 KB |
| testcase_08 | AC | 250 ms
50,016 KB |
| testcase_09 | AC | 257 ms
50,100 KB |
| testcase_10 | AC | 257 ms
50,084 KB |
| testcase_11 | AC | 257 ms
50,148 KB |
| testcase_12 | AC | 259 ms
50,240 KB |
| testcase_13 | AC | 252 ms
50,004 KB |
| testcase_14 | AC | 255 ms
50,076 KB |
| testcase_15 | AC | 250 ms
50,164 KB |
| testcase_16 | AC | 258 ms
50,264 KB |
| testcase_17 | AC | 255 ms
50,136 KB |
| testcase_18 | AC | 255 ms
50,060 KB |
| testcase_19 | AC | 259 ms
50,108 KB |
| testcase_20 | AC | 256 ms
50,228 KB |
| testcase_21 | AC | 257 ms
50,108 KB |
| testcase_22 | AC | 261 ms
50,108 KB |
コンパイルメッセージ
Main.kt:15:10: warning: parameter 'args' is never used
fun main(args: Array<String>) {
^
Main.kt:257:76: warning: unnecessary non-null assertion (!!) on a non-null receiver of type Long
fun max(vararg values: Long) = if (values.isEmpty()) -INF else values.max()!!
^
Main.kt:258:75: warning: unnecessary non-null assertion (!!) on a non-null receiver of type Long
fun min(vararg values: Long) = if (values.isEmpty()) INF else values.min()!!
^
ソースコード
import java.io.*
import java.lang.*
import java.math.*
import java.util.*
// Constant
val sc = FastScanner()
val pw = PrintWriter(System.out)
const val MOD = 1000000007L
const val INF = 9223372036854775807L
// Main
fun main(args: Array<String>) {
solve()
pw.flush()
}
// Global
fun solve() {
val n = nextLong()
val a = nextLongAry(n)
val b = nextLongAry(n)
val aPerm = Permutation(n)
aPerm.init()
var win = 0
var battle = 0
while (aPerm.hasNext()) {
val aStep = aPerm.nextPerm()
val bPerm = Permutation(n)
bPerm.init()
while (bPerm.hasNext()) {
val bStep = bPerm.nextPerm()
var aSum = 0L
var bSum = 0L
for (i in 0 until n) {
val aNow = a[aStep[i]]
val bNow = b[bStep[i]]
if(aNow > bNow) aSum++
else if(bNow > aNow) bSum++
}
battle++
if(aSum > bSum) win++
}
}
println(win.toDouble() / battle)
}
// Rule
operator fun String.get(index: Long): Char {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
return this[index.toInt()]
}
operator fun CharArray.get(index: Long): Char {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
return this[index.toInt()]
}
operator fun CharArray.set(index: Long, value: Char) {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
this[index.toInt()] = value
}
operator fun IntArray.get(index: Long): Int {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
return this[index.toInt()]
}
operator fun IntArray.set(index: Long, value: Int) {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
this[index.toInt()] = value
}
operator fun LongArray.get(index: Long): Long {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
return this[index.toInt()]
}
operator fun LongArray.set(index: Long, value: Long) {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
this[index.toInt()] = value
}
operator fun DoubleArray.get(index: Long): Double {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
return this[index.toInt()]
}
operator fun DoubleArray.set(index: Long, value: Double) {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
this[index.toInt()] = value
}
operator fun <T> Array<T>.get(index: Long): T {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
return this[index.toInt()]
}
operator fun <T> Array<T>.set(index: Long, value: T) {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
this[index.toInt()] = value
}
operator fun <T> MutableList<T>.get(index: Long): T {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
return this[index.toInt()]
}
operator fun <T> MutableList<T>.set(index: Long, value: T) {
if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
this[index.toInt()] = value
}
val LongArray.siz: Long
get() = size.toLong()
val <T> Array<T>.siz: Long
get() = size.toLong()
val <T> MutableList<T>.siz: Long
get() = size.toLong()
val <T> MutableSet<T>.siz: Long
get() = size.toLong()
val String.len: Long
get() = length.toLong()
// Output
fun println(v: String) {
pw.println(v)
}
fun print(v: String) {
pw.print(v)
}
// Input
fun next() = sc.next()
fun nextLong() = sc.nextLong()
fun nextLongs() = readLine()!!.split(" ").map { it.toLong() }
fun nextDouble() = next().toDouble()
fun nextAry(n: Long): Array<String> {
val ary = ary(n)
for (i in 0 until n) ary[i] = next()
return ary
}
fun nextLongAry(n: Long): LongArray {
val ary = longAry(n)
for (i in 0 until n) ary[i] = nextLong()
return ary
}
fun nextDoubleAry(n: Long): DoubleArray {
val ary = doubleAry(n)
for (i in 0 until n) ary[i] = nextDouble()
return ary
}
// Statement
fun ary(n: Long, init: String = "") = Array(n.toInt()) { init }
fun charAry(n: Long, init: Char = ' ') = CharArray(n.toInt()) { init }
fun longAry(n: Long, init: Long = 0L) = LongArray(n.toInt()) { init }
fun doubleAry(n: Long, init: Double = 0.0) = DoubleArray(n.toInt()) { init }
fun boolAry(n: Long, init: Boolean = false) = Array(n.toInt()) { init }
fun nodeAry(n: Long) = Array(n.toInt()) { Node(it.toLong()) }
fun ary2(n: Long, m: Long, init: String = "") = Array(n.toInt()) { ary(m, init) }
fun charAry2(n: Long, m: Long, init: Char = ' ') = Array(n.toInt()) { charAry(m, init) }
fun longAry2(n: Long, m: Long, init: Long = 0) = Array(n.toInt()) { longAry(m, init) }
fun doubleAry2(n: Long, m: Long, init: Double = 0.0) = Array(n.toInt()) { doubleAry(m, init) }
fun boolAry2(n: Long, m: Long, init: Boolean = false) = Array(n.toInt()) { boolAry(m, init) }
fun ary3(n: Long, m: Long, k: Long, init: String = "") = Array(n.toInt()) { ary2(m, k, init) }
fun charAry3(n: Long, m: Long, k: Long, init: Char = ' ') = Array(n.toInt()) { charAry2(m, k, init) }
fun longAry3(n: Long, m: Long, k: Long, init: Long = 0L) = Array(n.toInt()) { longAry2(m, k, init) }
fun doubleAry3(n: Long, m: Long, k: Long, init: Double = 0.0) = Array(n.toInt()) { doubleAry2(m, k, init) }
fun boolAry3(n: Long, m: Long, k: Long, init: Boolean = false) = Array(n.toInt()) { boolAry2(m, k, init) }
fun list() = mutableListOf<String>()
fun longList() = mutableListOf<Long>()
fun doubleList() = mutableListOf<Double>()
fun strSet() = mutableSetOf<String>()
fun longSet() = mutableSetOf<Long>()
fun doubleSet() = mutableSetOf<Double>()
fun <E, V> map() = mutableMapOf<E, V>()
// Monoid
val addFunc = {a: Long, b: Long -> a + b}
val mulFunc = {a: Long, b: Long -> a * b}
val maxFunc = {a: Long, b: Long -> max(a, b)}
val minFunc = {a: Long, b: Long -> min(a, b)}
val gcdFunc = {a: Long, b: Long -> gcd(a, b)}
val lcmFunc = {a: Long, b: Long -> lcm(a, b)}
val xorFunc = {a: Long, b: Long -> a xor b}
fun calc(a: Long, b: Long, op: (Long, Long) -> Long) = op(a, b)
// Extension
fun LongArray.lowerBound(n: Long): Long {
var ok = this.size.toLong()
var ng = -1L
while (abs(ok - ng) > 1) {
val mid = (ok + ng) / 2
if (this[mid] >= n) ok = mid
else ng = mid
}
return ok
}
fun DoubleArray.lowerBound(n: Double): Long {
var ok = this.size.toLong()
var ng = -1L
while (abs(ok - ng) > 1) {
val mid = (ok + ng) / 2
if (this[mid] >= n) ok = mid
else ng = mid
}
return ok
}
fun MutableList<Long>.longLowerBound(n: Long): Long {
var ok = this.size.toLong()
var ng = -1L
while (abs(ok - ng) > 1) {
val mid = (ok + ng) / 2
if (this[mid] >= n) ok = mid
else ng = mid
}
return ok
}
fun MutableList<Double>.doubleLowerBound(n: Double): Long {
var ok = this.size.toLong()
var ng = -1L
while (abs(ok - ng) > 1) {
val mid = (ok + ng) / 2
if (this[mid] >= n) ok = mid
else ng = mid
}
return ok
}
fun LongArray.cumsum(op: (Long, Long) -> Long): LongArray {
val s = longAry(this.size + 1L)
s[1] = this[0]
for (i in 1 until this.size) s[i + 1] = calc(s[i], this[i], op)
return s
}
fun MutableMap<String, Int>.counting(n: Long) {
repeat(n.toInt()) {
val a = next()
if (this.containsKey(a)) this[a] = this[a]!! + 1
else this[a] = 1
}
}
fun MutableMap<Long, Int>.longCounting(n: Long) {
repeat(n.toInt()) {
val a = nextLong()
if (this.containsKey(a)) this[a] = this[a]!! + 1
else this[a] = 1
}
}
// Mathematics
fun abs(n: Long): Long = Math.abs(n)
fun abs(n: Double): Double = Math.abs(n)
fun max(vararg values: Long) = if (values.isEmpty()) -INF else values.max()!!
fun min(vararg values: Long) = if (values.isEmpty()) INF else values.min()!!
tailrec fun gcd(a: Long, b: Long): Long = if (b == 0L) a else if (a % b == 0L) b else gcd(b, (a % b))
fun lcm(a: Long, b: Long): Long = a / gcd(a, b) * b
fun erathos(n: Long): LongArray {
val res = LongArray(n.toInt() + 1) { it.toLong() }
for (i in 2..n) {
if(i * i > n) break
for (j in i * i..n step i) {
if(res[j] == j) res[j] = i
}
}
res[0] = -1L
res[1] = -1L
return res
}
fun modAdd(a: Long, b: Long) = if(a + b >= MOD) a + b - MOD else a + b
fun modpow(a: Long, n: Long, p: Long = MOD): Long {
var res = 1L
var ar = a
var nr = n
while (nr > 0) {
if ((nr and 1) == 1L) res = res * ar % p
ar = ar * ar % p
nr = nr shr 1
}
return res
}
fun modinv(a: Long, p: Long = MOD): Long = modpow(a, p - 2, p)
fun ncr(n: Long, r: Long): Long {
var a = 1L
var b = 1L
for (i in 1..r) {
a = a * (n + 1 - i) % MOD
b = b * i % MOD
}
return modinv(b, MOD) * a % MOD
}
class Combination(private val max: Long) {
private val fac = longAry(max)
private val finv = longAry(max)
private val inv = longAry(max)
private val p = MOD
fun init() {
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for (i in 2 until max) {
fac[i] = fac[i - 1] * i % p
inv[i] = p - inv[p % i] * (p / i) % p;
finv[i] = finv[i - 1] * inv[i] % p
}
}
fun com(n: Long, r: Long): Long = if (n < r || (n < 0 || r < 0)) 0L else fac[n] * (finv[r] * finv[n - r] % p) % p
}
class Permutation(private val n: Long, private var searched: Long = 0L, private var nextIndex: Long = 0L) {
private val size = fact(n)
private val permList = longAry2(size, n)
private tailrec fun fact(n: Long, ans: Long = 1L): Long {
return if (n == 0L) ans
else fact(n - 1, ans * n)
}
fun init() {
create(0, longAry(n), boolAry(n))
}
private fun create(num: Long, list: LongArray, flag: Array<Boolean>) {
if (num == n) {
permList[searched] = list.copyOf()
searched++
}
for (i in 0 until n) {
if (flag[i]) continue
list[num] = i
flag[i] = true
create(num + 1, list, flag)
flag[i] = false
}
}
fun hasNext(): Boolean {
return if (nextIndex < size) {
true
} else {
nextIndex = 0
false
}
}
fun nextPerm(): LongArray = permList[nextIndex++]
}
// String
fun zAlgo(s: String): LongArray {
val n = s.len
val res = longAry(n)
var i = 1L
var j = 0L
while(i < n) {
while (i + j < n && s[j] == s[i + j]) j++
res[i] = j
if(j == 0L) {
i++
continue
}
var k = 1L
while (i + k < n && k + res[k] < j) {
res[i + k] = res[k]
k++
}
i += k
j -= k
}
return res
}
// Graph
data class Node(val id: Long, var past: Long = -1, val edges: MutableList<Edge> = mutableListOf())
data class Edge(val from: Long, val to: Long, val cost: Long = 1L)
fun dfs(nodes: Array<Node>, now: Long, seen: Array<Boolean>) {
seen[now] = true
for (edge in nodes[now].edges) {
if (seen[edge.to]) continue
dfs(nodes, edge.to, seen)
}
}
fun bfs(nodes: Array<Node>, start: Long): LongArray {
val queue = ArrayDeque<Long>()
queue.add(start)
val dist = longAry(nodes.size.toLong(), -1L)
dist[start] = 0L
while (queue.isNotEmpty()) {
val now = queue.poll()
for (edge in nodes[now].edges) {
if (dist[edge.to] != -1L) continue
dist[edge.to] = dist[now] + 1
queue.add(edge.to)
}
}
return dist
}
fun dijkstra(nodes: Array<Node>, start: Long): LongArray {
val queue = PriorityQueue<Pair<Long, Long>>(16) { x, y ->
return@PriorityQueue when {
x.second < y.second -> -1
x.second > y.second -> 1
else -> 0
}
}
queue.add(Pair(start, 0L))
val dist = longAry(nodes.size.toLong(), INF / 2)
dist[start] = 0
while (queue.isNotEmpty()) {
val now = queue.poll()
val v = now.first
if (dist[v] < now.second) continue
for (e in nodes[v].edges) {
if(dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost
queue.add(Pair(e.to, dist[e.to]))
}
}
}
return dist
}
class GridGraph(
private val h: Long,
private val w: Long,
val nodes: Array<Node> = Array((h * w).toInt()) { Node(it.toLong()) },
private val edges: IntArray = IntArray((h * w).toInt()) { 0 }
) {
private val up = 1
private val right = 2
private val down = 4
private val left = 8
private val queue: ArrayDeque<Long> = ArrayDeque()
private val startPos = longList()
private fun pos(y: Long, x: Long) = y * w + x
fun canUp(v: Long) = (edges[v] and 1) == 1
fun canRight(v: Long) = ((edges[v] shr 1) and 1) == 1
fun canDown(v: Long) = ((edges[v] shr 2) and 1) == 1
fun canLeft(v: Long) = ((edges[v] shr 3) and 1) == 1
fun init(s: Array<String>, check: Char = '.', road: Char = '.', start: Char = 'S') {
for (i in 0 until h) {
for (j in 0 until w) {
if(s[i][j] != check && s[i][j] != start) continue
if(i > 0 && s[i - 1][j] == road) edges[pos(i, j)] += up
if(i < h - 1 && s[i + 1][j] == road) edges[pos(i, j)] += down
if(j > 0 && s[i][j - 1] == road) edges[pos(i, j)] += left
if(j < w - 1 && s[i][j + 1] == road) edges[pos(i, j)] += right
if(s[i][j] == start) {
queue.add(pos(i, j))
startPos.add(pos(i, j))
}
}
}
}
fun addStart(y: Long, x: Long) {
startPos.add(pos(y, x))
queue.add(pos(y, x))
}
fun bfs(): LongArray {
val dist = longAry(h * w, -1L)
for (i in startPos) {
dist[i] = 0L
}
while (queue.isNotEmpty()) {
val v = queue.poll()
if(canUp(v) && dist[v - w] == -1L) {
queue.add(v - w)
dist[v - w] = dist[v] + 1L
}
if(canDown(v) && dist[v + w] == -1L) {
queue.add(v + w)
dist[v + w] = dist[v] + 1L
}
if(canLeft(v) && dist[v - 1] == -1L) {
queue.add(v - 1)
dist[v - 1] = dist[v] + 1L
}
if(canRight(v) && dist[v + 1] == -1L) {
queue.add(v + 1)
dist[v + 1] = dist[v] + 1L
}
}
return dist
}
}
// Data Structure
class UnionFind(size: Long) {
private val par = LongArray(size.toInt()) { it.toLong() }
private val size = longAry(size, 1L)
private val diffWeight = longAry(size, 0L)
fun root(x: Long): Long {
return if (par[x] == x) {
x
} else {
val r = root(par[x])
diffWeight[x] += diffWeight[par[x]]
par[x] = r
par[x]
}
}
fun weight(x: Long): Long {
root(x)
return diffWeight[x]
}
fun diff(x: Long, y: Long) = abs(weight(y) - weight(x))
fun same(x: Long, y: Long): Boolean = root(x) == root(y)
fun unite(x: Long, y: Long, d: Long) {
var w = d
w += weight(x)
w -= weight(y)
var a = root(x)
var b = root(y)
if (a == b) return
if (size[a] < size[b]) {
var tmp = a
a = b
b = tmp
w = -w
}
size[a] += size[b]
par[b] = a
diffWeight[b] = w
}
fun size(x: Long): Long = size[root(x)]
}
class SegmentTree(
private val a: LongArray,
private val op: (Long, Long) -> Long,
private val def: Long = 0,
private val size: Int = a.size,
private val n: Int = Integer.highestOneBit(size) shl 1
) {
private val nodes = longAry(2L * n - 1, def)
fun init() {
for (i in 0 until size) nodes[i + n - 1] = a[i]
for (i in n - 2 downTo 0) nodes[i] = calc(nodes[2 * i + 1], nodes[2 * i + 2], op)
}
fun update(x: Long, value: Long) {
var index = x + n - 1
nodes[index] = value
while (index > 0) {
index = (index - 1) / 2
nodes[index] = calc(nodes[2 * index + 1], nodes[2 * index + 2], op)
}
}
fun get(a: Long, b: Long) = getSub(a, b, 0L, 0L, n.toLong())
private fun getSub(a: Long, b: Long, k: Long, l: Long, r: Long): Long {
return when {
r <= a || b <= l -> def
a <= l && r <= b -> nodes[k]
else -> {
val vl = getSub(a, b, k * 2 + 1, l, (l + r) / 2)
val vr = getSub(a, b, k * 2 + 2, (l + r) / 2, r)
calc(vl, vr, op)
}
}
}
fun joinToString(separator: String) = nodes.drop(n - 1).take(size).joinToString(separator)
}
// Scanner
class FastScanner {
private val sin: InputStream = System.`in`
private val buffer: ByteArray = ByteArray(1024) { 0 }
private var ptr = 0
private var buflen = 0
private fun hasNextByte(): Boolean {
return when {
ptr < buflen -> true
else -> {
ptr = 0
buflen = sin.read(buffer)
buflen > 0
}
}
}
private fun readByte(): Int {
return when {
hasNextByte() -> buffer[ptr++].toInt()
else -> -1
}
}
private fun isPrintableChar(c: Int) = c in 33..126
fun hasNext(): Boolean {
while (hasNextByte() && !isPrintableChar(buffer[ptr].toInt())) ptr++
return hasNextByte()
}
fun next(): String {
if (!hasNext()) throw NoSuchElementException()
val sb = StringBuilder()
var b = readByte()
while (isPrintableChar(b)) {
sb.appendCodePoint(b)
b = readByte()
}
return sb.toString()
}
fun nextLong(): Long {
if (!hasNext()) throw NoSuchElementException()
var n = 0L
var minus = false
var b = readByte()
if (b.toChar() == '-') {
minus = true
b = readByte()
}
if (b.toChar() !in '0'..'9') throw NumberFormatException()
while (true) {
when {
b.toChar() in '0'..'9' -> {
n *= 10
n += b.toChar() - '0'
}
b == -1 || !isPrintableChar(b) -> return if (minus) -n else n
else -> throw NumberFormatException()
}
b = readByte()
}
}
// "The world doesn't need you."
//
// fun nextInt(): Int {
// val nl = nextLong()
// if (nl !in Int.MIN_VALUE..Int.MAX_VALUE) throw NumberFormatException()
// return nl.toInt()
// }
}