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

提出ソース

結果

問題	No.2308 [Cherry 5th Tune B] もしかして、真?
ユーザー	👑 Kazun
提出日時	2023-05-06 04:01:57
言語	PyPy3 (7.3.15)
結果	AC
実行時間	603 ms / 2,000 ms
コード長	9,868 bytes
コンパイル時間	358 ms
コンパイル使用メモリ	82,304 KB
実行使用メモリ	143,620 KB
最終ジャッジ日時	2024-05-10 04:49:56
合計ジャッジ時間	22,921 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	44 ms 54,400 KB
testcase_01	AC	502 ms 113,344 KB
testcase_02	AC	561 ms 134,028 KB
testcase_03	AC	516 ms 112,200 KB
testcase_04	AC	523 ms 113,652 KB
testcase_05	AC	534 ms 125,308 KB
testcase_06	AC	552 ms 137,080 KB
testcase_07	AC	553 ms 121,364 KB
testcase_08	AC	574 ms 129,732 KB
testcase_09	AC	572 ms 130,316 KB
testcase_10	AC	531 ms 113,816 KB
testcase_11	AC	543 ms 122,264 KB
testcase_12	AC	541 ms 124,164 KB
testcase_13	AC	552 ms 123,376 KB
testcase_14	AC	543 ms 122,272 KB
testcase_15	AC	546 ms 123,668 KB
testcase_16	AC	555 ms 123,836 KB
testcase_17	AC	545 ms 124,472 KB
testcase_18	AC	550 ms 123,960 KB
testcase_19	AC	548 ms 123,544 KB
testcase_20	AC	558 ms 123,936 KB
testcase_21	AC	603 ms 143,248 KB
testcase_22	AC	596 ms 143,108 KB
testcase_23	AC	592 ms 143,620 KB
testcase_24	AC	594 ms 143,284 KB
testcase_25	AC	602 ms 143,360 KB
testcase_26	AC	595 ms 143,020 KB
testcase_27	AC	590 ms 143,116 KB
testcase_28	AC	597 ms 143,228 KB
testcase_29	AC	602 ms 143,104 KB
testcase_30	AC	589 ms 143,112 KB
testcase_31	AC	436 ms 142,124 KB
testcase_32	AC	435 ms 141,700 KB
testcase_33	AC	436 ms 141,840 KB
testcase_34	AC	481 ms 142,512 KB
testcase_35	AC	481 ms 142,516 KB
testcase_36	AC	483 ms 142,476 KB
testcase_37	AC	293 ms 79,416 KB
testcase_38	AC	540 ms 125,028 KB

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

ソースコード

raw source code

class Fenwick_Tree:
    def __init__(self, N, A=None):
        self.N=N
        if A==None:
            self.data=[0]*N
        else:
            assert len(A)==N
            self.data=A
            self.__build()

    def __build(self):
        data=self.data
        for i in range(1, self.N+1):
            if i+(i&(-i))<=self.N:
                data[i+(i&(-i))-1]+=data[i-1]

    def add(self, i, x):
        i+=1
        data=self.data
        while i<=self.N:
            data[i-1]+=x
            i+=i&(-i)

    def sum(self, i):
        S=0
        data=self.data
        while i:
            S+=data[i-1]
            i-=i&(-i)
        return S

    def range_sum(self,l,r):
        return self.sum(r)-self.sum(l)

    def bisect_left(self, x, default=-1):
        i=0
        k=1<<self.N.bit_length()
        data=self.data

        while k:
            if i+k<=self.N and data[i+k-1]<x:
                x-=self.data[i+k-1]
                i+=k
            k>>=1
        return i if x else default

    def bisect_right(self, x, default=-1):
        i=0
        k=1<<self.N.bit_length()
        data=self.data

        while k:
            if i+k<=self.N and data[i+k-1]<=x:
                x-=self.data[i+k-1]
                i+=k
            k>>=1
        return i if i<self.N else default

class Ordered_Set:
    def __init__(self, N, multiple=False, S=None):
        self.N=N
        self.multiple=bool(multiple)

        if (not multiple) and S:
            S=[1 if S[i] else 0 for i in range(N)]

        self.Fenwick=Fenwick_Tree(N,S)
        self.__card=self.Fenwick.sum(N)

    def __contains__(self, x):
        return bool(self.count(x))

    def count(self, x):
        return self.Fenwick.range_sum(x,x+1)

    def __len__(self):
        return self.__card

    def __bool__(self):
        return bool(len(self))

    def add(self, x, k=1):
        """ x を k 個 (多重集合のとき) 加える.

        """

        if (not self.multiple) and (x in self):
            return

        if not self.multiple:
            k=1

        self.Fenwick.add(x,k)
        self.__card+=k

    def discard(self, x, k=1):
        """ x を k 個 (多重集合のとき) 削除する.

        x: int
        k: k=-1 とすると, x を全て削除する.
        """

        if x not in self:
            return

        if k==-1:
            k=self.count(x)
        elif not self.multiple:
            k=1

        self.Fenwick.add(x,-k)
        self.__card-=k

    def remove(self, x):
        """ x を k 個 (多重集合のとき) 削除する.

        x: int
        k: k=-1 とすると, x を全て削除する.
        """

        if  x not in self:
            raise KeyError(x)

        if k==-1:
            k=self.count(x)
        elif not self.multiple:
            k=1

        self.Fenwick.add(x, -k)
        self.__card-=k

    def get(self, index, default=-1):
        size=len(self)
        if size<=index or size+index<0:
            return default

        if index<0:
            index+=size

        return self.Fenwick.bisect_left(index+1)

    def __getitem__(self, index):
        size=len(self)
        if size<=index or size+index<0:
            raise IndexError

        if index<0:
            index+=size

        return self.Fenwick.bisect_left(index+1)

    def get_min(self, default=-1):
        return self.get(0, default)

    def pop_min(self):
        y=self.get_min()
        if y==-1:
            raise IndexError
        self.remove(y)
        return y

    def get_max(self, default=-1):
        return self.get(-1, default)

    def pop_max(self):
        y=self.get_max()
        if y==-1:
            raise IndexError
        self.remove(y)
        return y

    def index(self, x, mode=False, default=-1):
        """ S[k]=x を満たす k を求める.

        x: int
        mode: False のときは k の最小値, True の時は k の最大値 (多重集合のとき有用)
        """

        if x not in self:
            return default

        if mode:
            return self.Fenwick.sum(x+1)-1
        else:
            return self.Fenwick.sum(x)

    def previous(self, x, mode=True, default=-1):
        """ S に含まれる x 以下の要素のうち, 最大値を求める.

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

        if mode:
            x+=1

        if x>=0:
            return self.Fenwick.bisect_left(self.Fenwick.sum(x), default)
        else:
            return default

    def next(self, x, mode=True, default=-1):
        """ S に含まれる x 以上の要素のうち, 最大値を求める.

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

        if not mode:
            x+=1
        return self.Fenwick.bisect_right(self.Fenwick.sum(x), default)

    def less_count(self, x, mode=False):
        """ x 未満の元の個数を求める.

        x: int
        mode: mode=True ならば, "未満" が "以下" になる.
        """

        if mode:
            x+=1
        return self.Fenwick.sum(x)

    def more_count(self, x, mode=False):
        """ x より大きい元の個数を求める.

        x: int
        mode: mode=True ならば, "より大きい" が "以上" になる.
        """

        return len(self)-self.less_count(x, not mode)

    def kth_min(self, k, default=-1):
        """ k 番目に小さい元を求める.

        """

        if 1<=k<=len(self):
            return self[k-1]
        else:
            return default

    def kth_max(self, k, default=-1):
        """ k 番目に大きい元を求める.

        """

        if 1<=k<=len(self):
            return self[~(k-1)]
        else:
            return default

#==================================================
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 insert_front(self, x, y):
        """ x の前に y を挿入する.

        """

        z=self.__front[x]
        self.connect(y,x)
        if z!=-1:
            self.connect(z,y)

    def insert_back(self, x, y):
        """ x の後に y を挿入する.

        """

        z=self.__back[x]
        self.connect(x,y)
        if z!=-1:
            self.connect(y,z)

    def head(self, x):
        """ x が属する弱連結成分の先頭を求める.
        """

        while self.__front[x]!=-1:
            x=self.__front[x]
        return x

    def tail(self, x):
        """ 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=list(input().split())
    S=list(map(int,input().split()))

    A=[X[i]=="True" for i in range(N)]

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

    U=Ordered_Set(N, S=[1]*N)
    for j in range(N-1):
        r=U.kth_min(S[j]+1)
        p=D.previous(r); q=r-1

        if Y[q]=="and":
            op=AND
        elif Y[q]=="or":
            op=OR
        elif Y[q]=="xor":
            op=XOR
        else:
            op=IMP

        A[p]=op(A[p],A[r])
        U.discard(r)
        D.extract(r)

    return A[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

結果

テストケース

ソースコード