結果

問題 No.3143 Colorless Green Parentheses Sleep Furiously
ユーザー detteiuu
提出日時 2025-05-16 23:02:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 238 ms / 2,000 ms
コード長 5,412 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 81,988 KB
実行使用メモリ 106,708 KB
最終ジャッジ日時 2025-05-17 00:34:45
合計ジャッジ時間 9,187 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://github.com/tatyam-prime/SortedSet/blob/main/BucketList.py
import math
from typing import Generic, Iterable, Iterator, TypeVar
from collections import defaultdict
from bisect import bisect_left, bisect_right
T = TypeVar('T')

class BucketList(Generic[T]):
    BUCKET_RATIO = 16
    SPLIT_RATIO = 24
    
    def __init__(self, a: Iterable[T] = []) -> None:
        a = list(a)
        n = self.size = len(a)
        num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
        self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]

    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 __eq__(self, other) -> bool:
        if len(self) != len(other): return False
        for x, y in zip(self, other):
            if x != y: return False
        return True
    
    def __len__(self) -> int:
        return self.size
    
    def __repr__(self) -> str:
        return "BucketList" + str(self.a)
    
    def __str__(self) -> str:
        return str(list(self))

    def __contains__(self, x: T) -> bool:
        "Return True if x is in the bucket list. / O(N)"
        for y in self:
            if x == y: return True
        return False
    
    def _insert(self, a: list[T], b: int, i: int, x: T) -> None:
        a.insert(i, x)
        self.size += 1
        if len(a) > len(self.a) * self.SPLIT_RATIO:
            mid = len(a) >> 1
            self.a[b:b+1] = [a[:mid], a[mid:]]

    def insert(self, i: int, x: T) -> None:
        "Insert x at the i-th position. / O(√N)"
        if self.size == 0:
            if i != 0 and i != -1: raise IndexError
            self.a = [[x]]
            self.size = 1
            return
        if i < 0:
            for b, a in enumerate(reversed(self.a)):
                i += len(a)
                if i >= 0: return self._insert(a, len(self.a) + ~b, i, x)
        else:
            for b, a in enumerate(self.a):
                if i <= len(a): return self._insert(a, b, i, x)
                i -= len(a)

    def append(self, x: T) -> None:
        "Append x to the end of the list. / amortized O(1)"
        a = self.a[-1]
        return self._insert(a, len(self.a) - 1, len(a), x)
    
    def extend(self, a: Iterable[T]) -> None:
        for x in a: self.append(x)
    
    def __getitem__(self, i: int) -> T:
        if i < 0:
            for a in reversed(self.a):
                i += len(a)
                if i >= 0: return a[i]
        else:
            for a in self.a:
                if i < len(a): return a[i]
                i -= len(a)
        raise IndexError
    
    def _pop(self, a: list[T], b: int, i: int) -> T:
        ans = a.pop(i)
        self.size -= 1
        if not a: del self.a[b]
        return ans
    
    def pop(self, i: int = -1) -> T:
        "Remove and return the i-th element. / O(√N) / O(-i) if i < 0"
        if i < 0:
            for b, a in enumerate(reversed(self.a)):
                i += len(a)
                if i >= 0: return self._pop(a, ~b, i)
        else:
            for b, a in enumerate(self.a):
                if i < len(a): return self._pop(a, b, i)
                i -= len(a)
        raise IndexError

    def count(self, x: T) -> int:
        "Return the number of occurrences of x. / O(N)"
        return sum(1 for y in self if x == y)

    def index(self, x: T) -> int:
        "Return the index of the first occurrence of x, raise ValueError if not found. / O(N)"
        for i, y in enumerate(self):
            if x == y: return i
        raise ValueError
    
    def remove(self, x: T) -> None:
        "Remove the first occurrence of x, raise ValueError if not found. / O(N)"
        self.pop(self.index(x))

    def clear(self) -> None:
        self.a = []
        self.size = 0

    def reverse(self) -> None:
        self.a.reverse()
        for a in self.a: a.reverse()

    def copy(self) -> 'BucketList[T]':
        return BucketList(self)

N, K = map(int, input().split())
S = ["("] + list(input()) + [")"]

def judge(S):
    stack = []
    for s in S:
        if s == "(":
            stack.append(s)
        else:
            if stack:
                stack.pop()
            else:
                return False
    return True if not stack else False

if not judge(S[1:-1]):
    exit(print("No"))

stack = []
pair = [-1]*len(S)
SUM = 0
D = defaultdict(list)
E = []
for i, s in enumerate(S):
    if s == "(":
        stack.append(i)
        SUM += 1
    else:
        pair[i] = stack.pop()
        SUM -= 1
        D[SUM].append(i)
    E.append(SUM)

B = BucketList(S)
ADD = []
SUM = 0
for i, s in enumerate(S):
    if s == ")":
        a = E[i]+1
        r, l = bisect_left(D[a], i), bisect_right(D[a], pair[i])
        b = r-l
        if b == 0:
            ADD.append(("1+1", i))
            SUM += 2
        elif b == 1:
            ADD.append(("+1", i))
            SUM += 1
        else:
            for j in range(l, r-1):
                ADD.append(("+", D[a][j]+1))
if SUM <= K:
    if SUM < K:
        ADD.append(("+1"*(K-SUM), len(S)-1))
    cnt = 0
    ADD.sort(key=lambda x:x[1])
    for s, idx in ADD:
        B.insert(idx+cnt, s)
        cnt += 1
    B.pop(0)
    B.pop(-1)
    print("Yes")
    print("".join(B))
else:
    print("No")
0