結果
| 問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2023-04-24 21:22:14 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 735 ms / 2,000 ms |
| コード長 | 10,101 bytes |
| コンパイル時間 | 222 ms |
| コンパイル使用メモリ | 82,280 KB |
| 実行使用メモリ | 141,028 KB |
| 最終ジャッジ日時 | 2024-12-18 01:54:16 |
| 合計ジャッジ時間 | 27,598 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 39 |
ソースコード
" 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)])))