Решение
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.min
import kotlin.math.max
private const val MAX_TIME = 10000
private const val INF = Int.MAX_VALUE
private lateinit var tree: IntArray
private lateinit var counts: IntArray
private fun buildTree(node: Int, start: Int, end: Int) {
if (start == end) {
tree[node] = if (start in 1..MAX_TIME) counts[start] else INF
} else {
val mid = start + (end - start) / 2
buildTree(2 * node, start, mid)
buildTree(2 * node + 1, mid + 1, end)
tree[node] = min(tree[2 * node], tree[2 * node + 1])
}
}
private fun queryTree(node: Int, start: Int, end: Int, l: Int, r: Int): Int {
if (r < start || end < l || start > end) return INF
if (l <= start && end <= r) return tree[node]
val mid = start + (end - start) / 2
val leftMin = queryTree(2 * node, start, mid, l, r)
val rightMin = queryTree(2 * node + 1, mid + 1, end, l, r)
return min(leftMin, rightMin)
}
private fun solve(reader: BufferedReader, writer: BufferedWriter) {
val line = reader.readLine() ?: ""
val parts = line.split(" ").filter { it.isNotEmpty() }
if (parts.isEmpty()) {
writer.write("Wrong Answer\\n")
return
}
val n: Int
try {
n = parts[0].toInt()
} catch (e: NumberFormatException) {
writer.write("Wrong Answer\\n")
return
}
if (parts.size != 1 + 2 * n || n < 0) {
writer.write("Wrong Answer\\n")
return
}
val guards = mutableListOf<Pair<Int, Int>>()
val delta = IntArray(MAX_TIME + 2) { 0 }
var hasNonCoveringGuard = false
try {
for (i in 0 until n) {
val indexA = 1 + 2 * i
val indexB = 1 + 2 * i + 1
val a = parts[indexA].toInt()
val b = parts[indexB].toInt()
guards.add(Pair(a, b))
if (a >= b) {
hasNonCoveringGuard = true
} else {
delta[a + 1]++
if (b + 1 <= MAX_TIME + 1) {
delta[b + 1]--
}
}
}
} catch (e: Exception) {
writer.write("Wrong Answer\\n")
return
}
counts = IntArray(MAX_TIME + 1)
var currentGuards = 0
var isFullyCovered = true
if (n == 0 && MAX_TIME > 0) {
isFullyCovered = false
} else if (n > 0) {
for (t in 1..MAX_TIME) {
currentGuards += delta[t]
if (currentGuards <= 0) {
isFullyCovered = false
break
}
counts[t] = currentGuards
}
} else {
isFullyCovered = false
}
if (!isFullyCovered || hasNonCoveringGuard) {
writer.write("Wrong Answer\\n")
return
}
val treeSize = 4 * (MAX_TIME + 1)
tree = IntArray(treeSize) { INF }
buildTree(1, 1, MAX_TIME)
var allEssential = true
for ((a, b) in guards) {
val queryStart = a + 1
val queryEnd = b
val minCountInInterval = queryTree(1, 1, MAX_TIME, queryStart, queryEnd)
if (minCountInInterval > 1) {
allEssential = false
break
}
}
if (allEssential) {
writer.write("Accepted\\n")
} else {
writer.write("Wrong Answer\\n")
}
}
fun main() {
val reader = BufferedReader(InputStreamReader(System.`in`))
val writer = BufferedWriter(OutputStreamWriter(System.out))
val k = reader.readLine().toInt()
repeat(k) {
solve(reader, writer)
}
writer.flush()
reader.close()
writer.close()
}