-
Notifications
You must be signed in to change notification settings - Fork 0
/
P2PUpdate.kt
73 lines (58 loc) · 2.46 KB
/
P2PUpdate.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package setsandmaps
import java.io.File
fun main() {
val input = File("input.txt").bufferedReader()
val (n, packetsCount) = input.readLine().split(' ').map { it.toInt() }
val elements = MutableList(n) { MutableList(packetsCount) { false } }
elements[0] = MutableList(packetsCount) { true }
val closedOn = MutableList(n) { -1 }
closedOn[0] = 0
val packetsCountList = MutableList(packetsCount) { 1 }
val packetsCountListByElement = MutableList(n) { 0 }
packetsCountListByElement[0] = packetsCount
val receivedFrom = MutableList(n) { HashMap<Int, Int>() }
var closedCount = 1
var i = 1
while (closedCount < n) {
val requests = HashMap<Int, ArrayList<List<Int>>>()
val packetsSorted = List(packetsCount) { listOf(it, packetsCountList[it]) }.sortedBy { it[1] }
elements.forEachIndexed { index, packets ->
if (closedOn[index] == -1) {
val packet =
packetsSorted
.first { !packets[it[0]] }[0]
val requestTo =
elements
.indices
.filter { i -> elements[i][packet] && i != index }
.minBy { i -> packetsCountListByElement[i] }
if (!requests.containsKey(requestTo)) requests[requestTo] = ArrayList()
requests[requestTo]!!.add(listOf(index, packet))
}
}
val transfers = HashMap<Int, List<Int>>()
requests.forEach { (requestTo, requestsList) ->
transfers[requestTo] = requestsList.maxWith(
compareBy(
{ (request, _) -> receivedFrom[requestTo][request] },
{ (request, _) -> -packetsCountListByElement[request] }
)
)
}
transfers.forEach { (requestTo, list) ->
val (requestFrom, packet) = list
elements[requestFrom][packet] = true
packetsCountList[packet]++
packetsCountListByElement[requestFrom]++
receivedFrom[requestFrom][requestTo] = receivedFrom[requestFrom].getOrDefault(requestTo, 0) + 1
}
elements.indices.forEach { index ->
if (closedOn[index] == -1 && packetsCountListByElement[index] == packetsCount) {
closedOn[index] = i
closedCount++
}
}
i++
}
println(closedOn.filterIndexed { j, _ -> j != 0 }.joinToString(" "))
}