QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113359 | #5466. Permutation Compression | kemuniku | WA | 18ms | 9564kb | Python3 | 5.1kb | 2023-06-17 10:36:33 | 2023-06-17 10:36:35 |
Judging History
answer
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')
class SortedMultiset(Generic[T]):
BUCKET_RATIO = 50
REBUILD_RATIO = 170
def _build(self, a=None) -> None:
"Evenly divide `a` into buckets."
if a is None: a = list(self)
size = self.size = len(a)
bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]
def __init__(self, a: Iterable[T] = []) -> None:
"Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
a = list(a)
if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
a = sorted(a)
self._build(a)
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i: yield j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i): yield j
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedMultiset" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _find_bucket(self, x: T) -> List[T]:
"Find the bucket which should contain x. self must not be empty."
for a in self.a:
if x <= a[-1]: return a
return a
def __contains__(self, x: T) -> bool:
if self.size == 0: return False
a = self._find_bucket(x)
i = bisect_left(a, x)
return i != len(a) and a[i] == x
def count(self, x: T) -> int:
"Count the number of x."
return self.index_right(x) - self.index(x)
def add(self, x: T) -> None:
"Add an element. / O(√N)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return
a = self._find_bucket(x)
insort(a, x)
self.size += 1
if len(a) > len(self.a) * self.REBUILD_RATIO:
self._build()
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0: return False
a = self._find_bucket(x)
i = bisect_left(a, x)
if i == len(a) or a[i] != x: return False
a.pop(i)
self.size -= 1
if len(a) == 0: self._build()
return True
def lt(self, x: T) -> Union[T, None]:
"Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] < x:
return a[bisect_left(a, x) - 1]
def le(self, x: T) -> Union[T, None]:
"Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] <= x:
return a[bisect_right(a, x) - 1]
def gt(self, x: T) -> Union[T, None]:
"Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
if a[-1] > x:
return a[bisect_right(a, x)]
def ge(self, x: T) -> Union[T, None]:
"Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
if a[-1] >= x:
return a[bisect_left(a, x)]
def __getitem__(self, x: int) -> T:
"Return the x-th element, or IndexError if it doesn't exist."
if x < 0: x += self.size
if x < 0: raise IndexError
for a in self.a:
if x < len(a): return a[x]
x -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
def solve():
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
L = list(map(int,input().split()))
X = []
rB = list(reversed(B))
now = 0
for i in range(N):
if A[i] == rB[-1]:
rB.pop()
if now != 0:
X.append(now)
now = 0
if len(rB) == 0:
if N-(i+1) != 0:
X.append(N-(i+1))
break
else:
now += 1
else:
return ("NO")
X.sort()
SL = SortedMultiset(L)
for x in X:
while x != 0:
y = SL.le(x)
if y == None:
return "NO"
x -= y
SL.discard(y)
return "YES"
for _ in range(int(input())):
print(solve())
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 9464kb
input:
3 5 2 3 5 1 3 2 4 5 2 1 2 4 5 5 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 3 2 2 3 1 2 3 2 2 3
output:
YES YES NO
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 18ms
memory: 9564kb
input:
100 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 2 1 1 1 2 1 2 6 1 5 3 4 2 5 6 1 3 5 2 1 1 1 6 1 6 2 1 3 6 4 5 1 4 1 2 2 1 4 3 3 2 2 1 3 2 1 3 2 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1 2 1 2 4 4 3 2 1 3 4 2 1 3 4 4 3 1 1 1 1 1 1 1 6 5 1 6 2 5 4 3 1 6 2 4 3 1 4 1 1 1 1 1 1 6 5 3 3 6 1 4 5 2 3 6 1 4 2 3 3 4 4 3 4 3 4 ...
output:
YES NO NO YES YES YES YES YES YES YES YES NO YES NO YES NO YES YES YES YES YES YES NO YES YES NO YES NO YES NO YES YES YES YES YES YES YES YES NO NO NO YES YES YES NO YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES YES YES YES YES NO YES NO YES NO YES YES YES YES YES...
result:
wrong answer 2nd lines differ - expected: 'YES', found: 'NO'