#360455 (Nim) No.4 おもりと天秤

提出ソース
結果

問題	No.4 おもりと天秤
ユーザー	Mpikumin
提出日時	2019-07-18 15:21:23
言語	Nim (2.0.2)
結果	AC
実行時間	8 ms / 5,000 ms
コード長	13,957 bytes
コンパイル時間	2,438 ms
コンパイル使用メモリ	62,160 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-02 05:49:39
合計ジャッジ時間	3,296 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	7 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	8 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	8 ms 5,376 KB
testcase_10	AC	8 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	6 ms 5,376 KB
testcase_19	AC	7 ms 5,376 KB
testcase_20	AC	7 ms 5,376 KB
testcase_21	AC	7 ms 5,376 KB
testcase_22	AC	6 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
###################
###   utility   ###
###################
type lint = int64
template exit = quit 0
proc write[T]( x :T ) = stdout.write( $x )
# proc make[T]( f :proc():T ) :T = f()
proc alloc( T :typedesc ) :ptr T = cast[ptr T]( T.sizeof.alloc )
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)


################
###   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


###################
###   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     # [1, 100]
    W = int.read(N)  # [2, 100]
    sum = make[int]:
        for w in W: result += w

if sum mod 2 == 1:
    "impossible".echo
    exit

var dp = Tens[bool]( N+1, sum+1 )
dp[0, 0] = true
for i in N:
    for j in sum:
        if dp[i, j]:
            dp[i+1, j] = true
            dp[i+1, j+W[i]] = true

if dp[N, sum div 2]:
    "possible".echo
else:
    "impossible".echo
yukicoder

結果

テストケース

ソースコード
