結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー |
👑 |
提出日時 | 2024-05-04 16:36:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 535 ms / 2,000 ms |
コード長 | 2,719 bytes |
コンパイル時間 | 260 ms |
コンパイル使用メモリ | 82,232 KB |
実行使用メモリ | 131,156 KB |
最終ジャッジ日時 | 2024-11-26 05:27:32 |
合計ジャッジ時間 | 19,050 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
53,016 KB |
testcase_01 | AC | 463 ms
105,268 KB |
testcase_02 | AC | 417 ms
123,120 KB |
testcase_03 | AC | 397 ms
104,236 KB |
testcase_04 | AC | 398 ms
107,732 KB |
testcase_05 | AC | 465 ms
105,420 KB |
testcase_06 | AC | 415 ms
116,872 KB |
testcase_07 | AC | 484 ms
110,700 KB |
testcase_08 | AC | 502 ms
120,256 KB |
testcase_09 | AC | 442 ms
119,864 KB |
testcase_10 | AC | 521 ms
107,848 KB |
testcase_11 | AC | 514 ms
112,300 KB |
testcase_12 | AC | 525 ms
114,708 KB |
testcase_13 | AC | 518 ms
119,688 KB |
testcase_14 | AC | 516 ms
112,660 KB |
testcase_15 | AC | 535 ms
111,632 KB |
testcase_16 | AC | 512 ms
110,992 KB |
testcase_17 | AC | 511 ms
112,340 KB |
testcase_18 | AC | 525 ms
113,468 KB |
testcase_19 | AC | 520 ms
113,128 KB |
testcase_20 | AC | 520 ms
110,700 KB |
testcase_21 | AC | 467 ms
131,024 KB |
testcase_22 | AC | 479 ms
131,032 KB |
testcase_23 | AC | 474 ms
130,524 KB |
testcase_24 | AC | 476 ms
130,964 KB |
testcase_25 | AC | 461 ms
130,632 KB |
testcase_26 | AC | 465 ms
130,680 KB |
testcase_27 | AC | 473 ms
131,008 KB |
testcase_28 | AC | 479 ms
131,136 KB |
testcase_29 | AC | 472 ms
130,352 KB |
testcase_30 | AC | 475 ms
131,156 KB |
testcase_31 | AC | 261 ms
128,136 KB |
testcase_32 | AC | 272 ms
128,208 KB |
testcase_33 | AC | 278 ms
128,724 KB |
testcase_34 | AC | 296 ms
129,916 KB |
testcase_35 | AC | 292 ms
129,696 KB |
testcase_36 | AC | 299 ms
129,836 KB |
testcase_37 | AC | 254 ms
78,376 KB |
testcase_38 | AC | 505 ms
125,664 KB |
ソースコード
class UnionFind: def __init__(self, n): self.n = n self.par = [-1] * n self.group_ = n self.R = [i for i in range(n)] def find(self, x): if self.par[x] < 0: return x lst = [] while self.par[x] >= 0: lst.append(x) x = self.par[x] for y in lst: self.par[y] = x return x def unite(self, x, y): x = self.find(x) y = self.find(y) if x == y: return False if self.par[x] > self.par[y]: x, y = y, x self.par[x] += self.par[y] self.par[y] = x self.group_ -= 1 self.R[x] = max(self.R[x], self.R[y]) return True def size(self, x): return -self.par[self.find(x)] def same(self, x, y): return self.find(x) == self.find(y) @property def group(self): return self.group_ class BIT: def __init__(self, n): self.n = n self.data = [0] * (n + 1) if n == 0: self.n0 = 0 else: self.n0 = 1 << (n.bit_length() - 1) def sum_(self, i): s = 0 while i > 0: s += self.data[i] i -= i & -i return s def sum(self, l, r=-1): if r == -1: return self.sum_(l) else: return self.sum_(r) - self.sum_(l) def get(self, i): return self.sum(i, i + 1) def add(self, i, x): i += 1 while i <= self.n: self.data[i] += x i += i & -i def lower_bound(self, x): if x <= 0: return 0 i = 0 k = self.n0 while k > 0: if i + k <= self.n and self.data[i + k] < x: x -= self.data[i + k] i += k k //= 2 return i + 1 def solve(): n = int(input()) X = [True if x[0] == "T" else False for x in input().split()] Y = input().split() S = list(map(int, input().split())) bit = BIT(n) for i in range(n): bit.add(i, 1) for i, s in enumerate(S): p = bit.lower_bound(s) bit.add(p - 1, -1) S[i] = p - 1 UF = UnionFind(n) for s in S: y = Y[s] u = UF.find(s) v = UF.find(UF.R[u] + 1) UF.unite(u, v) p = UF.find(u) if y == "and": nex = X[u] & X[v] elif y == "or": nex = X[u] | X[v] elif y == "xor": nex = X[u] ^ X[v] else: if X[u]: nex = X[v] else: nex = True X[p] = nex print(X[UF.find(0)]) for _ in range(int(input())): solve()