#360506 (Nim) No.3 ビットすごろく

提出ソース
結果

問題	No.3 ビットすごろく
ユーザー	Mpikumin
提出日時	2019-07-18 21:22:35
言語	Nim (2.0.2)
結果	AC
実行時間	563 ms / 5,000 ms
コード長	14,895 bytes
コンパイル時間	2,862 ms
コンパイル使用メモリ	61,740 KB
実行使用メモリ	13,312 KB
最終ジャッジ日時	2024-07-01 09:25:36
合計ジャッジ時間	8,313 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	3 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	16 ms 6,944 KB
testcase_06	AC	3 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	7 ms 6,940 KB
testcase_09	AC	83 ms 6,940 KB
testcase_10	AC	219 ms 6,940 KB
testcase_11	AC	52 ms 6,944 KB
testcase_12	AC	13 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	188 ms 6,940 KB
testcase_15	AC	484 ms 10,880 KB
testcase_16	AC	280 ms 6,944 KB
testcase_17	AC	425 ms 10,624 KB
testcase_18	AC	3 ms 6,940 KB
testcase_19	AC	550 ms 13,184 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	197 ms 6,940 KB
testcase_23	AC	563 ms 13,184 KB
testcase_24	AC	556 ms 13,312 KB
testcase_25	AC	484 ms 10,880 KB
testcase_26	AC	1 ms 6,944 KB
testcase_27	AC	3 ms 6,940 KB
testcase_28	AC	265 ms 6,944 KB
testcase_29	AC	55 ms 6,944 KB
testcase_30	AC	2 ms 6,944 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	34 ms 6,940 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
###################
###   utility   ###
###################
type lint = int64
template exit = quit 0
proc write[T]( x :T ) = stdout.write( $x )
proc alloc( T :typedesc ) :ptr T = cast[ptr T]( T.sizeof.alloc )
proc make[T]( f :proc():T ) :T = f()
# template make[T]( body :untyped ) :T =
#     block:
#         proc f() :T =
#             body
#         f()


####################
###   function   ###
####################
proc less[T1,T2]( x :T1, y :T2 ) :bool = x < y
proc more[T1,T2]( x :T1, y :T2 ) :bool = x > y

proc add[T1,T2]( x :T1, y :T2 ) :T1 = x + y
proc mul[T1,T2]( x :T1, y :T2 ) :T1 = x * y

proc max[T1,T2]( x :T1, y :T2 ) :T1 = max(x, y)
proc min[T1,T2]( x :T1, y :T2 ) :T1 = min(x, y)

proc id[T]( x :T ) :T = x

####################
###   iterator   ###
####################
iterator items( p :(int,int) ) :int =
    let (L,R) = p
    for i in L..<R:
        yield i

iterator items( N :int ) :int =
    for i in 0..<N:
        yield i

iterator reverse( L, R :int ) :int =
    var i = R
    while i > L:
        i.dec
        yield i

iterator reverse( N :int ) :int =
    for i in reverse(0, N):
        yield i


################
###   vect   ###
################
type vect[T] = seq[T]

proc Vect[T]( n :int ): vect[T] =
    newSeq[T]( result, n )

proc Vect[T]( S :openArray[T] ) :vect[T] =
    result = Vect[T]( S.len )
    for i, e in S:
        result[i] = e

proc elem[T]( e :T, s :varargs[T] ) :bool =
    for a in s:
        if e == a: return true
    return false

proc countIf[T]( S :openArray[T], f :proc(x:T):bool ) :int =
    for e in S:
        if f(e):
            result.inc


################
###   tens   ###
################
type tens[T] = object
    data :vect[T]
    shape :vect[int]

proc Tens[T]( S :varargs[int] ) :tens[T] =
    var N :int = 1
    for s in S: N *= s
    result.data = Vect[T](N)
    result.shape = @S

proc `[]`[T]( t :tens[T], s :varargs[int] ) :T =
    var n = 0
    var r = 1
    for i in reverse(s.len):
        n += s[i] * r
        r *= t.shape[i]
    return t.data[n]

proc `[]=`[T]( t :var tens[T], s :varargs[int], e :T ) =
    var n = 0
    var r = 1
    for i in reverse(s.len):
        n += s[i] * r
        r *= t.shape[i]
    t.data[n] = e

iterator items[T]( t :tens[T] ) :T = items(t.data)


####################
###   priority   ###
####################
type priority[T] = object
    data :vect[T]
    compare :proc(x,y:T):bool

proc Priority[T]() :priority[T] =
    result.data = Vect[T](1)
    result.compare = less

proc Priority[T]( compare :proc(x,y:T):bool ) :priority[T] =
    result.data = Vect[T](1)
    result.compare = compare

proc exist[T]( p :priority[T] ) :bool = p.data.len > 0
proc push[T]( p :var priority[T], e :T ) =
    var n = p.data.len
    p.data.add(e)
    while n div 2 != 0 and p.compare( p.data[n], p.data[n div 2] ):
        swap( p.data[n], p.data[n div 2] )
        n = n div 2
proc front[T]( p :priority[T] ) :T = p.data[1]
proc trash[T]( p :var priority[T] ) =
    let N = p.data.len - 1
    p.data[1] = p.data[N]
    p.data.setLen(N)
    var n = 1
    while true:
        if n * 2 >= N: break
        if n * 2 + 1 >= N:
            if p.compare( p.data[n], p.data[n * 2] ): break
            swap( p.data[n], p.data[n * 2] )
            n = n * 2
            continue
        if not p.compare( p.data[n * 2], p.data[n] ) and
           not p.compare( p.data[n * 2 + 1], p.data[n] ):
            break
        if p.compare( p.data[n * 2], p.data[n * 2 + 1] ):
            swap( p.data[n], p.data[n * 2] )
            n = n * 2
        else:
            swap( p.data[n], p.data[n * 2 + 1] )
            n = n * 2 + 1
proc pop[T]( p :var priority[T] ) :T =
    result = p.front
    p.trash


################
###   mint   ###
################
const MOD :int = 1000000007
type mint = distinct int

proc Mint[I]( n :I ) :mint =
    var n = n.int mod MOD
    if n < 0: n = n + MOD
    return n.mint

proc `$`( m :mint ) :string = $m.int
proc `+`[I]( m: mint, n: I ) :mint = (m.int + n.int).Mint
proc `-`[I]( m: mint, n: I ) :mint = (m.int - n.int).Mint
proc `*`[I]( m: mint, n: I ) :mint = (m.int * n.int).Mint
proc `/`[I]( m :mint, n :I ) :mint =
    var
        a = n.int
        b = MOD
        u = 1
        v = 0
    while b > 0:
        var t = a div b
        a -= t * b
        u -= t * v
        swap( a, b )
        swap( u, v )
    return m * u

proc `div`[I]( m :mint, n :I ) :mint = m / n

proc `+=`[I]( m :var mint, n :I ) = m = m + n
proc `-=`[I]( m :var mint, n :I ) = m = m - n
proc `*=`[I]( m :var mint, n :I ) = m = m * n
proc `/=`[I]( m :var mint, n :I ) = m = m / n

proc `==`[I]( m :mint, n :I ) :bool = m.int == n.Mint.int

##################
###   number   ###
##################
proc `^`[T](n :T, m :int) :T =
    var n = n
    var m = m
    result = 1.T
    while m > 0:
        if m mod 2 != 0: result = result * n
        n = n * n
        m = m div 2

proc `%`[N,M]( n :N, m :M ) :N =
    result = n mod m.N
    if n < 0: result += m.N

proc fact[I]( n :I ) :I =
    var memo {.global.} :seq[I] = @[I(1)]
    if n.int >= memo.len:
        let m :int = memo.len
        memo.setLen(n.int + 1)
        for i in m..n.int:
            memo[i] = memo[i-1] * i
    return memo[n.int]

proc perm[N,K]( n :N, k :K ) :N =
    fact(n) div fact(n-k)

proc comb[N,K]( n :N, k :K ) :N =
    fact(n) div fact(k.N) div fact(n-k)

proc eratos( N :int ) :vect[bool] =
    result = Vect[bool](N+1)
    for i in (2,N+1): result[i] = true
    var i = 2
    while i * i <= N:
        if result[i]:
            var j = i * 2
            while j <= N:
                result[j] = false
                j += i
        i += 1


################
###   list   ###
################
const NodeSize = 256

type node[T] = object
    data :array[NodeSize,T]
    prev, next :ptr node[T]

type list[T] = object
    head,  tail :ptr node[T]
    first, last :int

proc List[T]() :list[T] =
    result.head = node[T].alloc
    result.tail = result.head

proc empty[T]( li :list[T] ) :bool =
    li.head == li.tail and li.first == li.last

proc exist[T]( li :list[T] ) :bool =
    not li.empty()

proc len[T]( li :list[T] ) :int =
    var now = li.head
    while now != nil:
        result += NodeSize
        now = now.next
    result -= NodeSize + li.first - li.last

proc mostLeft[T]( li :list[T] ) :T =
    li.head.data[li.first]

proc mostRight[T]( li :list[T] ) :T =
    if li.last == 0:
        li.tail.prev.data[NodeSize-1]
    else:
        li.tail.data[li.last-1]

proc pushLeft[T]( li :var list[T], e :T ) =
    if li.first == 0:
        li.head.prev = alloc( node[T] )
        li.head.prev.next = li.head
        li.head = li.head.prev
    li.first = (li.first - 1) % NodeSize
    li.head.data[li.first] = e

proc pushRight[T]( li :var list[T], e :T ) =
    li.tail.data[li.last] = e
    li.last = (li.last + 1) % NodeSize
    if li.last == 0:
        li.tail.next = alloc( node[T] )
        li.tail.next.prev = li.tail
        li.tail = li.tail.next

proc trashLeft[T]( li :var list[T] ) =
    li.first = (li.first + 1) mod NodeSize
    if li.first == 0:
        li.head = li.head.next
        li.head.prev.dealloc
        li.head.prev = nil

proc trashRight[T]( li :var list[T] ) =
    if li.last == 0:
        li.tail = li.tail.prev
        li.tail.next.dealloc
        li.tail.next = nil
    li.last = (li.last - 1) % NodeSize

proc popLeft[T]( li :var list[T] ) :T =
    result = li.mostLeft
    li.trashLeft

proc popRight[T]( li :var list[T] ) :T =
    result = li.mostRight
    li.trashRight

proc `[]`[T]( li :list[T], n :int ) :T =
    var p = li.head
    for _ in (n + li.first) div NodeSize: p = p.next
    return p.data[(li.first + n) % NodeSize]

proc `[]=`[T]( li :var list[T], n :int, e :T ) =
    var p = li.head
    for _ in (n + li.first) div NodeSize: p = p.next
    p.data[(li.first + n) % NodeSize] = e

iterator items[T]( li :list[T] ) :T =
    var i = li.first
    var now = li.head
    while now != li.tail:
        while i != NodeSize:
            yield now.data[i]
            i.inc
        i = 0
        now = now.next
    while i != li.last:
        yield now.data[i]
        i.inc

proc `$`[T]( li :list[T] ) :string =
    if li.empty: return "list[]"
    result = "list["
    for e in li:
        result &= $e
        result &= ", "
    result.setLen(result.len - 2)
    result &= "]"


#################
###   stack   ###
#################
type stack[T] = object
    data :list[T]
proc Stack[T]() :stack[T] = result.data = List[T]()
proc exist[T]( s :stack[T] ) :bool = s.data.exist
proc empty[T]( s :stack[T] ) :bool = s.data.empty
proc push[T]( s :var stack[T], e :T ) = s.data.pushRight(e)
proc front[T]( s :stack[T] ) :T = s.data.mostRight
proc trash[T]( s :var stack[T] ) = s.data.trashRight
proc pop[T]( s :var stack[T] ) :T = s.data.popRight


#################
###   queue   ###
#################
type queue[T] = object
    data :list[T]
proc Queue[T]() :queue[T] = result.data = List[T]()
proc exist[T]( q :queue[T] ) :bool = q.data.exist
proc empty[T]( q :queue[T] ) :bool = q.data.empty
proc push[T]( q :var queue[T], e :T ) = q.data.pushRight(e)
proc front[T]( q :queue[T] ) :T = q.data.mostLeft
proc trash[T]( q :var queue[T] ) :T = q.data.trashLeft
proc pop[T]( q: var queue[T] ) :T = q.data.popLeft


################
###   sort   ###
################
proc sort[T]( S :var openArray[T], compare :proc(x,y:T):bool ) =
    var stack = Stack[ (bool,int,int) ]()
    stack.push( (true, 0, S.len) )
    while stack.exist:
        var (B, L, R) = stack.pop
        if R - L < 2: continue
        if B:
            stack.push( (false, L, R) )
            stack.push( (true, L, (L+R) div 2) )
            stack.push( (true, (L+R) div 2, R) )
            continue

        var temp = Vect[T]( (L+R) div 2 - L )
        for i in temp.len: temp[i] = S[L+i]
        var (t, r) = (0, (L+R) div 2)
        for i in (L,R):
            if r == R or t != temp.len and compare(temp[t], S[r] ):
                S[i] = temp[t]
                t.inc
            else:
                S[i] = S[r]
                r.inc


proc sort[T]( S :var openArray[T] ) =
    S.sort less

proc sortF[T]( S :openArray[T], comp :proc(x,y:T):bool ) :vect[T] =
    result = Vect[T](S)
    sort[T](result,comp)

proc sortF[T]( S :openArray[T] ) :vect[T] =
    result = Vect[T](S)
    result.sort


####################
###   min, max   ###
###################
proc argMax[T]( V :openArray[T] ) :int =
    var max = T.low
    for i, e in V:
        if e > max:
            result = i
            max = e

proc upperBound[T]( L, R :T, f :proc(n:T):bool ) :T =
    var (ok, ng) = (L, R)
    while ng - ok > 1:
        let mid = (ng + ok) div 2
        if f( mid ):
            ok = mid
        else:
            ng = mid
    return ok

proc lowerBound[T]( L, R :T, f :proc(n:T):bool ) :T =
    upperBound( L, R, proc(n:T) :bool = not f(n) ) + 1


################
###   read   ###
################
proc read( T :typedesc ) :T =
    proc getchar() :char {.header:"stdio.h",importc:"getchar".}

    when T is char:
        result = getchar()
        discard getchar()

    when T is string:
        result = ""
        while true:
            var c = getchar()
            if c.elem( ' ', '\10', '\255' ): break
            result.add c

    when T is (int or lint or mint):
        var
            sign = 1
            c = getchar()

        if c == '-':
            sign = -1
            c = getchar()

        while '0' <= c and c <= '9':
            result *= 10
            result += c.int() - '0'.int()
            c = getchar()

        result *= sign

    when T is tuple:
        for r in result.fields:
            r = r.type.read

proc read( T :typedesc, N :int ) :vect[T] =
    result = Vect[T](N)
    for i in N:
        result[i] = T.read


####################
###   disjoint   ###
####################
type disjoint = object
    data :vect[int]

proc Disjoint( n :int ) :disjoint =
    result.data = Vect[int](n)
    for i in n: result.data[i] = -1

proc find( d :var disjoint, n :int ) :int =
    if d.data[n] < 0: return n
    d.data[n] = d.find( d.data[n] )
    return d.data[n]

proc union( d :var disjoint, n, m :int ) =
    var n = d.find(n)
    var m = d.find(m)
    if n == m: return
    if d.data[m] < d.data[n]: swap( n, m )
    d.data[m] += d.data[n]
    d.data[n] = m

proc same( d :var disjoint, n, m :int ) :bool =
    d.find(n) == d.find(m)

proc size( d :var disjoint, n :int ) :int =
    - d.data[d.find(n)]


###############
###   bit   ###
###############
iterator allBit[I]() :I =
    var i :I = 1.I
    while i != 0.I:
        yield i
        i = i shl 1.I

proc bitCount( b :int ) :int =
    var b :int64 = b
    b = (b        and 0x5555555555555555) +
        (b shr  1 and 0x5555555555555555)
    b = (b        and 0x3333333333333333) +
        (b shr  2 and 0x3333333333333333)
    b = (b        and 0x0f0f0f0f0f0f0f0f) +
        (b shr  4 and 0x0f0f0f0f0f0f0f0f)
    b = (b        and 0x00ff00ff00ff00ff) +
        (b shr  8 and 0x00ff00ff00ff00ff)
    b = (b        and 0x0000ffff0000ffff) +
        (b shr 16 and 0x0000ffff0000ffff)
    b = (b        and 0x00000000ffffffff) +
        (b shr 32 and 0x00000000ffffffff)
    result = b.int


###################
###   segment   ###
###################
type segment[T] = object
    size :int
    data :vect[T]
    op :proc(x,y:T):T

proc Segment[T]( V :vect[T], e :T, F :proc(x,y:T):T ) :segment[T] =
    result.op = F
    result.size = 1
    while result.size < V.len: result.size = result.size shl 1
    result.data = Vect[T](result.size * 2)
    for i in V.len: result.data[result.size + i] = V[i]
    for i in (V.len,result.size): result.data[result.size+i] = e
    for i in reverse(1,result.size):
        result.data[i] = F( result.data[2*i], result.data[2*i+1] )

proc update[T]( S :var segment[T], K :int, X :T ) =
    var k = (K + S.size) div 2
    S.data[k] = X
    while(K != 0):
        S.data[k] = S.op( S.data[k*2], S.data[2*k+1] )
        k = k div 2

proc query[T]( S :segment, L, R :int ) :T =
    var
        L = L + S.size + 1
        R = R + S.size - 1
        X = S.data[L-1]
        Y = S.data[R]

    while L < R:
        if (L and 1) != 0: X = S.op( X, S.data[L] )
        L.inc
        R.dec
        if (R and 1) != 0: Y = S.op( S.data[R], Y )

    return S.op(X, Y)


##########################
####                  ####
####       main       ####
####                  ####
##########################
let
    N = int.read

if N == 1:
    echo 1
    exit

var
    dp = Vect[int](N)
    q = Queue[(int,int)]()
q.push (1,1)

while q.exist:
    let (step,now) = q.pop
    dp[now] = step
    if now+bitCount(now) == N:
        echo step+1
        exit
    if now+bitCount(now) < N and dp[now+bitCount(now)] == 0:
        q.push (step+1, now+bitCount(now))
    if now-bitCount(now) >= 1 and dp[now-bitCount(now)] == 0:
        q.push (step+1, now-bitCount(now))

echo -1
yukicoder

結果

テストケース

ソースコード
