#760664 (Kotlin) No.1935 Water Simulation

• 問題: No.1935 Water Simulation
• ユーザー: ripity
• 提出日時: 2022-05-13 22:24:13
• 言語: Kotlin (1.9.23)
• 結果: AC
• 実行時間: 362 ms / 2,000 ms
• コード長: 8,594 bytes
• コンパイル時間: 21,795 ms
• コンパイル使用メモリ: 441,676 KB
• 実行使用メモリ: 53,124 KB
• 最終ジャッジ日時: 2023-09-29 09:55:40
• 合計ジャッジ時間: 33,335 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	298 ms; 52,784 KB
testcase_01	AC	299 ms; 52,764 KB
testcase_02	AC	296 ms; 52,764 KB
testcase_03	AC	294 ms; 52,712 KB
testcase_04	AC	293 ms; 52,792 KB
testcase_05	AC	293 ms; 52,796 KB
testcase_06	AC	289 ms; 53,124 KB
testcase_07	AC	291 ms; 52,796 KB
testcase_08	AC	296 ms; 52,952 KB
testcase_09	AC	293 ms; 52,768 KB
testcase_10	AC	290 ms; 52,776 KB
testcase_11	AC	290 ms; 52,724 KB
testcase_12	AC	291 ms; 52,644 KB
testcase_13	AC	293 ms; 52,788 KB
testcase_14	AC	297 ms; 52,800 KB
testcase_15	AC	293 ms; 52,708 KB
testcase_16	AC	297 ms; 52,868 KB
testcase_17	AC	297 ms; 52,764 KB
testcase_18	AC	295 ms; 52,940 KB
testcase_19	AC	295 ms; 52,656 KB
testcase_20	AC	362 ms; 52,760 KB
testcase_21	AC	292 ms; 52,712 KB
testcase_22	AC	295 ms; 52,732 KB
testcase_23	AC	296 ms; 52,736 KB
testcase_24	AC	290 ms; 52,792 KB
testcase_25	AC	294 ms; 52,808 KB
testcase_26	AC	298 ms; 52,832 KB
testcase_27	AC	292 ms; 52,824 KB
testcase_28	AC	292 ms; 52,648 KB
testcase_29	AC	295 ms; 52,652 KB
testcase_30	AC	295 ms; 52,804 KB
testcase_31	AC	291 ms; 52,784 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 */