結果
| 問題 | No.1935 Water Simulation |
| ユーザー |
 ripity
|
| 提出日時 | 2022-05-13 22:24:13 |
| 言語 | Kotlin (1.9.23) |
| 結果 |
AC
|
| 実行時間 | 342 ms / 2,000 ms |
| コード長 | 8,594 bytes |
| コンパイル時間 | 22,732 ms |
| コンパイル使用メモリ | 459,428 KB |
| 実行使用メモリ | 51,000 KB |
| 最終ジャッジ日時 | 2024-07-22 04:29:29 |
| 合計ジャッジ時間 | 32,596 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 312 ms
50,972 KB |
| testcase_01 | AC | 312 ms
51,000 KB |
| testcase_02 | AC | 311 ms
51,000 KB |
| testcase_03 | AC | 308 ms
50,996 KB |
| testcase_04 | AC | 309 ms
50,936 KB |
| testcase_05 | AC | 304 ms
50,852 KB |
| testcase_06 | AC | 309 ms
50,820 KB |
| testcase_07 | AC | 311 ms
50,780 KB |
| testcase_08 | AC | 324 ms
50,836 KB |
| testcase_09 | AC | 314 ms
50,780 KB |
| testcase_10 | AC | 314 ms
50,784 KB |
| testcase_11 | AC | 313 ms
50,680 KB |
| testcase_12 | AC | 342 ms
50,772 KB |
| testcase_13 | AC | 315 ms
50,884 KB |
| testcase_14 | AC | 312 ms
50,724 KB |
| testcase_15 | AC | 309 ms
50,892 KB |
| testcase_16 | AC | 311 ms
50,720 KB |
| testcase_17 | AC | 306 ms
50,760 KB |
| testcase_18 | AC | 306 ms
50,932 KB |
| testcase_19 | AC | 308 ms
50,696 KB |
| testcase_20 | AC | 312 ms
50,896 KB |
| testcase_21 | AC | 310 ms
50,804 KB |
| testcase_22 | AC | 313 ms
50,792 KB |
| testcase_23 | AC | 310 ms
50,904 KB |
| testcase_24 | AC | 307 ms
50,772 KB |
| testcase_25 | AC | 316 ms
50,908 KB |
| testcase_26 | AC | 309 ms
50,732 KB |
| testcase_27 | AC | 310 ms
50,692 KB |
| testcase_28 | AC | 309 ms
50,824 KB |
| testcase_29 | AC | 315 ms
50,812 KB |
| testcase_30 | AC | 311 ms
50,732 KB |
| testcase_31 | AC | 311 ms
50,688 KB |
ソースコード
import java.io.*
import java.util.*
import kotlin.math.*
val rnd = arrayOf(arrayOf(1826976902, 1879583235, 1939978176, 359874268, 1959452303, 1196702584, 526293443, 639760410, 70924354, 470040856, 1802414741, 409853810, 23675038, 963456727, 1875914531, 419762400, 1766138237, 1382260636, 1859162579, 1887585422, 2049271026, 1289060704, 1174113983, 1432068116, 413823016, 136708659, 188836927, 608119447, 947221719, 1443751279, 207933786, 9258642, 1400437776, 249449833, 803488404, 1475126320, 400606905, 1167237583, 1019259889, 859845444, 1521655579, 1361531188, 12618731, 1435600087, 1373000134, 1471816317, 1844408374, 77516185, 1879517471, 760091353, 1591413246, 1889910923, 928340749, 1219040155, 1735795349, 1287631713, 2057942640, 1659051243, 474756495, 2122405626, 1865502364, 762442580, 2016178815, 147097468, 1791806493, 482591528, 1716737969, 479040661, 17760393, 1807669380, 1125624455, 1409760561, 110501820, 485222790, 1675604254, 881981606, 1705789213, 1300181701, 1013893847, 40269466, 722373707, 920150758, 1341982638, 1739545407, 530229894, 804131242, 1838435494, 38100153, 197851422, 1059194097, 1229963295, 1924465242, 910960690, 34450337, 1078737020, 225345063, 1266530917, 1404253099, 946700154, 1556882255, 906208039), arrayOf(1870157423, 223879561, 1280910339, 576544694, 2136183012, 1832260901, 1627231269, 1830473486, 1678188215, 312415860, 690916637, 1827901061, 843447402, 1574129211, 1736565106, 1485404285, 1651380733, 1581973213, 724471593, 255591785, 554367338, 258265673, 725280612, 584012869, 1646508665, 1497589492, 142110147, 571114334, 868874541, 1228686886, 1457232391, 1261091122, 471493372, 1533817399, 1781916089, 1574674109, 2051642592, 35605214, 1559794439, 826605186, 311954657, 1948801853, 635620556, 282066928, 1934722568, 1665556747, 189713024, 145640523, 1867677960, 1521001285, 1150827252, 187260058, 703366885, 1230493953, 788094442, 1864115074, 945521892, 1674864068, 1768447167, 901576919, 1112136344, 553182314, 993927073, 1064836248, 613479507, 1407114461, 28531915, 2019852013, 2099311386, 634697137, 1140240905, 156653209, 1982838270, 930878257, 2021217599, 1156721898, 1791198745, 76634375, 1279747107, 846901251, 1735101543, 2040577661, 1116856775, 441825896, 1513833747, 730451028, 1710123117, 1344895217, 139695480, 762590766, 808424013, 1306701929, 747168134, 121263342, 266523332, 705987152, 341059243, 778807124, 252403090, 1726383474, 1403174732), arrayOf(585058011, 1969223517, 1282506490, 1290041472, 1000256978, 1378651711, 437058499, 683203721, 1649951809, 259117859, 1223068309, 1009439130, 2138880115, 759205477, 565916437, 1631498338, 360414174, 265581420, 525830029, 1711306149, 891298668, 420504655, 1583903489, 198983442, 1343729117, 1720575930, 1779630886, 242100970, 1228046234, 734318711, 1679945869, 691961634, 970595894, 1899888730, 1888896385, 722055885, 1285747956, 1064417939, 1608788809, 334198785, 1216822007, 861401250, 2080702466, 821133177, 1956190248, 1295731228, 1804770199, 1442131256, 641252615, 1291363320, 1010931305, 736561448, 1642831182, 648471418, 223998368, 36415884, 850179787, 703247852, 810818654, 975443376, 1471304811, 1855557602, 879854212, 128470286, 392971052, 691888592, 332242196, 1155643660, 42347985, 181828069, 1517504687, 1176226813, 1853208662, 893371652, 1706339123, 40614593, 1569928159, 1563011726, 2096374506, 1956008506, 723907310, 32603187, 1180892918, 1169193965, 989809177, 385568077, 1423333673, 1576752072, 1113403454, 535872340, 870905668, 109503891, 32855710, 250691557, 1101407909, 870319362, 1669138101, 509671108, 1641374597, 1512953142, 1484105615), arrayOf(2099281951, 1810993699, 1032741561, 1705295883, 1506131734, 947406175, 513448195, 1170481461, 876483178, 894291302, 1324300186, 1719914788, 1219081440, 1254849247, 46246888, 1500026148, 1215833864, 1072392333, 916959459, 165595608, 2130202762, 1507354933, 274121394, 1007827742, 272196859, 1340389231, 588941831, 1503787212, 624403655, 1523634857, 620233592, 508392919, 1515965839, 474099747, 1747618629, 1683045734, 1046972844, 1094210411, 1396732684, 1301034603, 1903316095, 1582321703, 1582717851, 1320765967, 123820597, 43496629, 1812568072, 356814030, 95467785, 23213975, 986431213, 1374778549, 2104174293, 1654882760, 38194779, 859869738, 1761593707, 1612276455, 1710683794, 1703861674, 1994948999, 2076900043, 803211714, 1427128586, 444570415, 6574859, 320983250, 771771517, 2031286644, 584886551, 980044597, 1691049286, 1671307402, 674044269, 1193706771, 1990597283, 1407628371, 1849819259, 2104019563, 918606280, 430305053, 1158880848, 1735730033, 1511413380, 1304521596, 615267999, 1861939131, 1667060302, 2064875547, 1723461630, 1491506041, 2023304790, 126475399, 2022180963, 1909058815, 1938587778, 1191943702, 1883614615, 136674699, 1790429392, 553484854))
fun main() {
solve()
pw.flush()
}
fun solve() {
var orgv = nextIntarr(4)
var v = Array<Int>(4) { if( it == 0 ) orgv[it] else 0 }
var N = nextLong()
val ms = mutableListOf(State(v, 0))
val mshash = mutableListOf(f(v, 0))
val rep: MutableList<State> = mutableListOf()
val hs = HashSet<Int>()
var bound: Int
hs.add(f(v, 0))
while(true) {
val ns = ms.last()
val i = ns.t
val j = (ns.t+1)%4
val k = min(v[i], orgv[j]-v[j])
v[i] -= k
v[j] += k
val nxs = State(v.copyOf(), j)
val hash = f(v, j)
// pw.println("$nxs $hash")
if( hs.contains(hash) ) {
bound = mshash.indexOf(hash)
for( idx in bound until ms.size ) {
rep.add(ms[idx])
}
break
}else {
ms.add(nxs)
hs.add(hash)
mshash.add(hash)
}
}
// pw.println(ms)
// pw.println(rep)
val ansv: Array<Int>
val mss = ms.size.toLong()
val rps = rep.size.toLong()
if( N < mss-rps ) {
ansv = ms[N.toInt()].v
}else {
N -= mss-rps
// pw.println(N)
ansv = rep[(N%rps).toInt()].v
}
ansv.forEach{ pw.print("$it ") }
pw.println()
}
fun f(v: Array<Int>, t: Int): Int = rnd[0][v[0]] xor rnd[1][v[1]] xor rnd[2][v[2]] xor rnd[3][v[3]] xor (119*t)
data class State(val v: Array<Int>, val t: Int)
/* struct begin */
data class Point(val x: Int, val y: Int)
data class Edge(val from: Int, val to: Int, val w: Long)
class BinaryIndexedTree(n: Int) {
val N = n
var a = Array<Long>(N+1) {0L}
fun sum(i: Int): Long {
var idx = i+1
var res = 0L
while( idx > 0 ) {
res += a[idx]
idx -= idx and (-idx)
}
return res
}
fun add(i: Int, x: Long) {
var idx = i+1
while( idx <= N ) {
a[idx] += x
idx += idx and (-idx)
}
}
}
class UnionFind(N: Int) {
var parent = Array<Int>(N) {it}
var rank = Array<Int>(N) {1}
var size = Array<Int>(N) {1}
fun root(x: Int): Int {
if( parent[x] == x ) {
return x
}else {
parent[x] = root(parent[x])
return parent[x]
}
}
fun unite(x: Int, y: Int) {
val rx = root(x)
val ry = root(y)
if( rx == ry ) return
if( rank[rx] > rank[ry] ) {
parent[ry] = rx
size[rx] += size[ry]
}else {
parent[rx] = ry
size[ry] += size[rx]
if( rank[rx] == rank[ry] ) rank[ry]++
}
}
fun same(x: Int, y: Int): Boolean = (root(x) == root(y))
fun getSize(x: Int): Int = size[root(x)]
}
/* struct end */
/* math begin */
fun intceil(x: Double) = ceil(x).toInt()
fun intfloor(x: Double) = floor(x).toInt()
fun gcd(x: Int, y: Int): Int {
var a = max(x, y)
var b = min(x, y)
var r: Int
do {
r = a%b
a = b
b = r
}while( r > 0 )
return a
}
/* math end */
/* I/O begin */
var st = StringTokenizer("")
val br = System.`in`.bufferedReader()
val pw = PrintWriter(System.out, false)
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextLine() = br.readLine()!!
fun nextDouble() = next().toDouble()
fun nextIntarr(n: Int) = Array<Int>(n) {nextInt()}
fun nextStrarr(n: Int) = Array<String>(n) {next()}
fun nextLongarr(n: Int) = Array<Long>(n) {nextLong()}
fun next(): String {
while( !st.hasMoreTokens() ) st = StringTokenizer(br.readLine()!!)
return st.nextToken()
}
/* I/O end */