結果

問題 No.387 ハンコ
コンテスト
ユーザー vwxyz
提出日時 2023-03-08 16:53:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,241 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 271,736 KB
最終ジャッジ日時 2024-09-18 02:34:57
合計ジャッジ時間 12,923 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class Bit_Set:
    def __init__(self,bit_set=[],word=64,complement=False):
        self.bit_set=bit_set
        self.word=word
        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>>64-n|x%(1<<64-n)<<n)
            prev=x
        while bit_set and bit_set[-1]==0:
            bit_set.pop()
        return Bit_Set(bit_set=bit_set,word=self.word,complement=self.complement)

    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)<<64-n)
        return Bit_Set(bit_set=bit_set,word=self.word,complement=self.complement)

    def __and__(self,other):
        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,word=self.word,complement=complement)

    def __xor__(self,other):
        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,word=self.word,complement=complement)

    def __or__(self,other):
        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,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 self.complement:
            self.clear_bit(x)
        else:
            self.set_bit(x)

    def remove(self,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 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 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|=Bit_Set([1])<<i
ans_set=Bit_Set()
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&(Bit_Set([1])<<i):
        ans="ODD"
    else:
        ans="EVEN"
    print(ans)
0