#862688 (PyPy3) No.2308 [Cherry 5th Tune B] もしかして、真?

提出ソース

結果

問題	No.2308 [Cherry 5th Tune B] もしかして、真?
ユーザー	👑 Kazun
提出日時	2023-04-24 21:22:14
言語	PyPy3 (7.3.15)
結果	AC
実行時間	734 ms / 2,000 ms
コード長	10,101 bytes
コンパイル時間	177 ms
コンパイル使用メモリ	82,496 KB
実行使用メモリ	141,104 KB
最終ジャッジ日時	2024-05-10 04:48:42
合計ジャッジ時間	27,975 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	42 ms 54,272 KB
testcase_01	AC	610 ms 117,608 KB
testcase_02	AC	641 ms 122,076 KB
testcase_03	AC	624 ms 116,068 KB
testcase_04	AC	626 ms 123,556 KB
testcase_05	AC	647 ms 121,716 KB
testcase_06	AC	678 ms 134,072 KB
testcase_07	AC	681 ms 138,820 KB
testcase_08	AC	699 ms 134,936 KB
testcase_09	AC	700 ms 134,968 KB
testcase_10	AC	643 ms 121,152 KB
testcase_11	AC	657 ms 125,152 KB
testcase_12	AC	668 ms 125,304 KB
testcase_13	AC	665 ms 126,456 KB
testcase_14	AC	677 ms 125,424 KB
testcase_15	AC	663 ms 126,688 KB
testcase_16	AC	658 ms 125,096 KB
testcase_17	AC	666 ms 125,096 KB
testcase_18	AC	656 ms 124,928 KB
testcase_19	AC	654 ms 126,724 KB
testcase_20	AC	671 ms 123,616 KB
testcase_21	AC	706 ms 140,268 KB
testcase_22	AC	734 ms 138,900 KB
testcase_23	AC	713 ms 139,304 KB
testcase_24	AC	727 ms 139,456 KB
testcase_25	AC	725 ms 139,744 KB
testcase_26	AC	717 ms 139,460 KB
testcase_27	AC	705 ms 139,952 KB
testcase_28	AC	713 ms 139,804 KB
testcase_29	AC	727 ms 139,744 KB
testcase_30	AC	723 ms 138,860 KB
testcase_31	AC	432 ms 138,312 KB
testcase_32	AC	423 ms 138,404 KB
testcase_33	AC	422 ms 138,160 KB
testcase_34	AC	478 ms 139,388 KB
testcase_35	AC	474 ms 139,216 KB
testcase_36	AC	469 ms 141,104 KB
testcase_37	AC	283 ms 80,420 KB
testcase_38	AC	662 ms 124,632 KB

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

ソースコード

raw source code

" Reference: https://qiita.com/tatyam/items/492c70ac4c955c055602"
# ※ 計算量が O(sqrt(N)) per query なので, 過度な期待はしないこと.

from bisect import bisect_left, bisect_right
class Sorted_Set:
    BUCKET_RATIO=50
    REBUILD_RATIO=170

    def __init__(self, A=[]):
        A=list(A)
        if not all(A[i]<A[i+1] for i in range(len(A)-1)):
            A=sorted(set(A))
        self.__build(A)
        return

    def __build(self, A=None):
        if A is None:
            A=list(self)

        self.N=N=len(A)
        K=1
        while self.BUCKET_RATIO*K*K<N:
            K+=1

        self.list=[A[N*i//K: N*(i+1)//K] for i in range(K)]

    def __iter__(self):
        for A in self.list:
            for a in A:
                yield a

    def __reversed__(self):
        for A in reversed(self.list):
            for a in reversed(A):
                yield a

    def __len__(self):
        return self.N

    def __bool__(self):
        return bool(self.N)

    def __str__(self):
        string=str(list(self))
        return "{"+string[1:-1]+"}"

    def __repr__(self):
        return "Sorted Set: "+str(self)

    def __find_bucket(self, x):
        for A in self.list:
            if x<=A[-1]:
                return A
        else:
            return A

    def __contains__(self, x):
        if self.N==0:
            return False

        A=self.__find_bucket(x)
        i=bisect_left(A,x)
        return i!=len(A) and A[i]==x

    def add(self, x):
        if self.N==0:
            self.list=[[x]]
            self.N+=1
            return True

        A=self.__find_bucket(x)
        i=bisect_left(A, x)

        if i!=len(A) and A[i]==x:
            return False # x が既に存在するので...

        A.insert(i,x)
        self.N+=1

        if len(A)>len(self.list)*self.REBUILD_RATIO:
            self.__build()
        return True

    def discard(self, x):
        if self.N==0:
            return False

        A=self.__find_bucket(x)
        i=bisect_left(A, x)

        if not(i!=len(A) and A[i]==x):
            return False # x が存在しないので...

        A.pop(i)
        self.N-=1

        if len(A)==0:
            self.__build()

        return True

    def remove(self, x):
        if not self.discard(x):
            raise KeyError(x)

    #=== get, pop

    def __getitem__(self, index):
        if index<0:
            index+=self.N
            if index<0:
                raise IndexError("index out of range")

        for A in self.list:
            if index<len(A):
                return A[index]
            index-=len(A)
        else:
            raise IndexError("index out of range")

    def get_min(self):
        if self.N==0:
            raise ValueError("This is empty set.")

        return self.list[0][0]

    def pop_min(self):
        if self.N==0:
            raise ValueError("This is empty set.")

        A=self.list[0]
        value=A.pop(0)
        self.N-=1

        if len(A)==0:
            self.__build()

        return value

    def get_max(self):
        if self.N==0:
            return ValueError("This is empty set.")

        return self.list[-1][-1]

    def pop_max(self):
        if self.N==0:
            raise ValueError("This is empty set.")

        A=self.list[-1]
        value=A.pop(-1)
        self.N-=1

        if len(A)==0:
            self.__build()

        return value

    #=== previous, next

    def previous(self, value, mode=False):
        """ S にある value 未満で最大の要素を返す (存在しない場合は None)

        mode: True のときは "未満" が "以下" になる.
        """

        if self.N==0:
            return None

        if mode:
            for A in reversed(self.list):
                if A[0]<=value:
                    return A[bisect_right(A,value)-1]
        else:
            for A in reversed(self.list):
                if A[0]<value:
                    return A[bisect_left(A,value)-1]

    def next(self, value, mode=False):
        """ S にある value より大きい最小の要素を返す (存在しない場合は None)

        mode: True のときは "より大きい" が "以上" になる.
        """

        if self.N==0:
            return None

        if mode:
            for A in self.list:
                if A[-1]>=value:
                    return A[bisect_left(A,value)]
        else:
            for A in self.list:
                if A[-1]>value:
                    return A[bisect_right(A,value)]

    #=== count
    def less_count(self, value, equal=False):
        """ a < value となる S の元 a の個数を求める.

        equal=True ならば, a < value が a <= value になる.
        """

        count=0
        if equal:
            for A in self.list:
                if A[-1]>value:
                    return count+bisect_right(A, value)
                count+=len(A)
        else:
            for A in self.list:
                if A[-1]>=value:
                    return count+bisect_left(A, value)
                count+=len(A)
        return count

    def more_count(self, value, equal=False):
        """ a > value となる S の元 a の個数を求める.

        equal=True ならば, a > value が a >= value になる.
        """

        return self.N-self.less_count(value, not equal)

    #===
    def is_upper_bound(self, x, equal=True):
        if self.N:
            a=self.list[-1][-1]
            return (a<x) or (bool(equal) and a==x)
        else:
            return True

    def is_lower_bound(self, x, equal=True):
        if self.N:
            a=self.list[0][0]
            return (x<a) or (bool(equal) and a==x)
        else:
            return True

    #=== index
    def index(self, value):
        index=0
        for A in self.list:
            if A[-1]>value:
                i=bisect_left(A, value)
                if A[i]==value:
                    return index+i
                else:
                    raise ValueError("{} is not in Set".format(value))
            index+=len(A)
        raise ValueError("{} is not in Set".format(value))

#==================================================
class Doubly_Linked_List:
    def __init__(self, N):
        self.__N=N
        self.__front=[-1]*N
        self.__back=[-1]*N

    def __len__(self):
        return self.__N

    def __str__(self):
        res=[]
        used=[0]*self.__N

        for x in range(self.__N):
            if used[x]:
                continue

            a=self.enumerate(x)
            for y in a:
                used[y]=1
            res.append(a)
        return str(res)

    def __repr__(self):
        return "[Doubly Linked List]: "+str(self)

    def previous(self, x, default=-1):
        return self.__front[x] if self.__front[x]!=-1 else default

    def next(self, x, default=-1):
        return self.__back[x] if self.__back[x]!=-1 else default

    def disconnect_front(self, x):
        """ x から前に伸びるリンクを削除する.

        """

        front=self.__front; back=self.__back

        y=front[x]
        if y>=0:
            front[x]=-1
            back[y]=-1

    def disconnect_back(self, x):
        """ x から後ろに伸びるリンクを削除する.

        """

        front=self.__front; back=self.__back

        y=back[x]
        if y>=0:
            back[x]=-1
            front[y]=-1

    def extract(self, x):
        """ x に接続するリンクを削除し, x の前後が存在するならば, それらをつなぐ.
        """

        a=self.__front[x]
        b=self.__back[x]

        self.disconnect_front(x)
        self.disconnect_back(x)

        if a!=-1 and b!=-1:
            self.connect(a,b)

    def connect(self, x, y):
        """ x から y へのリンクを生成する (すでにある x からのリンクと y へのリンクは削除される).

        """

        self.disconnect_back(x)
        self.disconnect_front(y)
        self.__back[x]=y
        self.__front[y]=x

    def head(self, x):
        while self.__front[x]!=-1:
            x=self.__front[x]
        return x

    def tail(self, x):
        while self.__back[x]!=-1:
            x=self.__back[x]
        return x

    def enumerate(self, x):
        """ x が属している弱連結成分を先頭から順に出力する.

        """

        x=self.head(x)
        res=[x]
        while self.__back[x]>=0:
            x=self.__back[x]
            res.append(x)
        return res

    def depth(self, x):
        dep=0
        while self.__front[x]!=-1:
            x=self.__front[x]
            dep+=1
        return dep

#==================================================
def AND(x,y):
    return (x and y)

def OR(x,y):
    return (x or y)

def XOR(x,y):
    return (x^y)

def IMP(x,y):
    return ((not x) or y)
#==================================================
def solve():
    N=int(input())
    X=list(input().split())
    Y=[None]+list(input().split())
    S=list(map(int,input().split()))

    X=[x=="True" for x in X]

    U=Sorted_Set(range(N))
    D=Doubly_Linked_List(N)
    for i in range(N-1):
        D.connect(i,i+1)

    for j in range(N-1):
        k=U[S[j]-1]
        kn=D.next(k)
        if Y[kn]=="and":
            op=AND
        elif Y[kn]=="or":
            op=OR
        elif Y[kn]=="xor":
            op=XOR
        else:
            op=IMP

        U.discard(kn)
        D.extract(kn)

        X[k]=op(X[k], X[kn])
        X[kn]=None

    return X[0]

#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write

T=int(input())
write("\n".join(map(str,[solve() for _ in range(T)])))

yukicoder

結果

テストケース

ソースコード