#847053 (PyPy3) No.387 ハンコ

提出ソース

結果

問題	No.387 ハンコ
ユーザー	vwxyz
提出日時	2023-03-09 22:43:53
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	6,779 bytes
コンパイル時間	217 ms
コンパイル使用メモリ	81,756 KB
実行使用メモリ	128,720 KB
最終ジャッジ日時	2023-10-18 06:31:02
合計ジャッジ時間	12,952 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	--	-
testcase_02	--	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
readline=sys.stdin.readline
from itertools import zip_longest

class Bit_Set:
    def __init__(self,x=None,bit_set=[],element_range=0,word=64,complement=False):
        self.word=word
        if x==None:
            self.bit_set=bit_set
        else:
            self.bit_set=[]
            while x:
                self.bit_set.append(x&((1<<self.word)-1))
                x>>=self.word
        self.element_range=element_range
        self.complement=complement

    def __contains__(self,x):
        if self.complement:
            return len(self.bit_set)<=x//self.word or ~(self.bit_set[x//self.word]&1<<x%self.word)
        else:
            return len(self.bit_set)>x//self.word and self.bit_set[x//self.word]&1<<x%self.word

    def __bool__(self):
        return self.bit_set or self.complement

    def __eq__(self,other):
        if len(self.bit_set)!=len(other.bit_set):
            return False
        if self.complement!=other.complement:
            return False
        for x,y in zip(self.bit_set,other.bit_set):
            if x!=y:
                return False
        return True

    def __ne__(self,other):
        if len(self.bit_set)!=len(other.bit_set):
            return True
        if self.complement!=other.complement:
            return True
        for x,y in zip(self.bit_set,other.bit_set):
            if x!=y:
                return True
        return False
    
    def __lshift__(self,n):
        bit_set=[0]*(n//self.word)
        n%=self.word
        prev=0
        for x in self.bit_set:
            bit_set.append(prev>>self.word-n|x%(1<<self.word-n)<<n)
            prev=x
        while bit_set and bit_set[-1]==0:
            bit_set.pop()
        bit_set=Bit_Set(bit_set=bit_set,element_range=self.element_range,word=self.word,complement=self.complement)
        bit_set.Adjust_Element_Range()
        return bit_set

    def __rshift__(self,n):
        bit_set=[]
        nn,n=divmod(n,self.word)
        for x,y in zip_longest(self.bit_set[nn:],self.bit_set[nn+1:],fillvalue=0):
            bit_set.append(x>>n|y%(1<<n)<<self.word-n)
        return Bit_Set(bit_set=bit_set,element_range=self.element_range,word=self.word,complement=self.complement)

    def __and__(self,other):
        if type(other)!=Bit_Set:
            other=Bit_Set(x=other,element_range=self.element_range,word=self.word,complement=False)
        complement=self.complement&other.complement
        bit_set=[(~x if self.complement else x)&(~y if other.complement else y) for x,y in zip_longest(self.bit_set,other.bit_set,fillvalue=0)]
        if complement:
            for i in range(len(bit_set)):
                bit_set[i]=~bit_set[i]
        while bit_set and bit_set[-1]==0:
            bit_set.pop()
        return Bit_Set(bit_set=bit_set,element_range=self.element_range,word=self.word,complement=complement)

    def __xor__(self,other):
        if type(other)!=Bit_Set:
            other=Bit_Set(x=other,element_range=self.element_range,word=self.word,complement=False)
        complement=self.complement^other.complement
        bit_set=[(~x if self.complement else x)^(~y if other.complement else y) for x,y in zip_longest(self.bit_set,other.bit_set,fillvalue=0)]
        if complement:
            for i in range(len(bit_set)):
                bit_set[i]=~bit_set[i]
        while bit_set and bit_set[-1]==0:
            bit_set.pop()
        return Bit_Set(bit_set=bit_set,element_range=self.element_range,word=self.word,complement=complement)

    def __or__(self,other):
        if type(other)!=Bit_Set:
            other=Bit_Set(x=other,element_range=self.element_range,word=self.word,complement=False)
        complement=self.complement|other.complement
        bit_set=[(~x if self.complement else x)|(~y if other.complement else y) for x,y in zip_longest(self.bit_set,other.bit_set,fillvalue=0)]
        if complement:
            for i in range(len(bit_set)):
                bit_set[i]=~bit_set[i]
        while bit_set and bit_set[-1]==0:
            bit_set.pop()
        return Bit_Set(bit_set=bit_set,element_range=self.element_range,word=self.word,complement=complement)

    def __str__(self):
        retu=[]
        for i,x in enumerate(self.bit_set):
            for j in range(self.word):
                if x&1<<j:
                    retu.append(i*self.word+j)
        return "{"+", ".join(map(str,retu))+"}"
    
    def __bool__(self):
        if self.bit_set:
            return True
        else:
            return False

    def set_bit(self,x):
        self.bit_set+=[0]*(x//self.word+1-len(self.bit_set))
        self.bit_set[x//self.word]^=1<<x%self.word

    def clear_bit(self,x):
        if len(self.bit_set)>x//self.word:
            self.bit_set[x//self.word]&=~(1<<x)
        while self.bit_set and self.bit_set[-1]==0:
            self.bit_set.pop()

    def add(self,x):
        if x<self.element_range:
            if self.complement:
                self.clear_bit(x)
            else:
                self.set_bit(x)

    def remove(self,x):
        assert self.element_range<=x
        if x in self:
            if self.complement:
                self.set_bit(x)
            else:
                self.clear_bit(x)
        else:
            raise KeyError(x)

    def discard(self,x):
        if x<self.element_range:
            if self.complement:
                self.set_bit(x)
            else:
                self.clear_bit(x)

    def pop(self):
        if self.bit_set:
            retu=len(self.bit-1)*self.word+self.bit_set[-1].bit_length()-1
        else:
            retu=None
        return retu

    def Find_First(self):
        if not self.bit_set:
            return None
        return (len(self.bit_set)-1)*self.word+(self.bit_set[-1]&-self.bit_set[-1]).bit_length()-1

    def Adjust_Element_Range(self):
        if self.element_range:
            while len(self.bit_set)>(self.element_range+self.word-1)//self.word:
                self.bit_set.pop()
            if len(self.bit_set)==(self.element_range+self.word-1)//self.word:
                self.bit_set[-1]&=(1<<(self.element_range-1)%self.word+1)-1

    def iter(self):
        for i,x in enumerate(self.bit_set):
            for j in range(self.word):
                if x&1<<j:
                    yield i*self.word+j

N=int(readline())
A=list(map(int,readline().split()))
for i in range(N):
    A[i]-=1
M=max(A)+1
idx=[[] for i in range(M)]
for i in range(N):
    idx[A[i]].append(i)
B=Bit_Set()
for i,b in enumerate(map(int,readline().split())):
    if b:
        B|=1<<i
ans_set=Bit_Set(element_range=10000000)
for a in range(M):
    AB=Bit_Set()
    for i in idx[a]:
        AB|=B<<i
    ans_set^=AB
for i in range(2*N-1):
    if ans_set&1<<i:
        ans="ODD"
    else:
        ans="EVEN"
    print(ans)

yukicoder

結果

テストケース

ソースコード