結果

問題 No.2740 Old Maid
ユーザー sk4rdsk4rd
提出日時 2024-04-20 18:41:34
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,173 bytes
コンパイル時間 656 ms
コンパイル使用メモリ 82,440 KB
実行使用メモリ 116,588 KB
最終ジャッジ日時 2024-04-20 18:41:59
合計ジャッジ時間 22,985 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 AC 476 ms
116,096 KB
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 376 ms
88,472 KB
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 AC 423 ms
88,528 KB
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 AC 37 ms
52,736 KB
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 AC 37 ms
53,424 KB
testcase_50 RE -
testcase_51 AC 41 ms
53,376 KB
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 AC 38 ms
53,632 KB
testcase_56 AC 37 ms
53,376 KB
testcase_57 RE -
testcase_58 RE -
testcase_59 RE -
testcase_60 AC 38 ms
53,888 KB
testcase_61 RE -
testcase_62 AC 38 ms
53,196 KB
testcase_63 AC 37 ms
53,196 KB
testcase_64 AC 38 ms
53,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n, self.m = n, 1 << (n-1).bit_length()
        self.data = [ide] * (self.m*2)
        self.func, self.ide = func, ide

    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.m+i] = x
        for i in range(self.m-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.m
        self.data[i] = x
        while i > 1:
            i >>= 1
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.m; r += self.m 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
  
    def get(self, i):
        return self.data[self.m+i]
    
    def get_data(self):
        return self.data[self.m:self.m+self.n]

    def __setitem__(self, idx, val):
        assert isinstance(idx, int) and -self.n <= idx < self.n
        self.update(idx % self.n, val)

    def __getitem__(self, idx):
        if isinstance(idx, slice):
            l, r, _ = idx.indices(self.n)
            assert l <= r
            return self.query(l, r)
        if isinstance(idx, int) and -self.n <= idx < self.n:
            return self.get(idx % self.n)
        raise AssertionError
class BIT:
    def __init__(self, val):
        if type(val) == int:
            self.n = val
            self.data = [0] * (self.n+1)
        elif type(val) == list:
            self.n = len(val)
            self.data = [0] * (self.n+1)
            self.build(val)
        else: raise TypeError(type(val))
    
    def build(self, data):
        for i in range(1, self.n+1):
            self.data[i] += data[i-1]
            j = i + (i & -i)
            if j <= self.n:
                self.data[j] += self.data[i]
    
    class _Element:
        def __init__(self, outer, i, val):
            self.outer = outer
            self.i = i
            self.val = val
        def __iadd__(self, x):
            self.outer.add(self.i, x)
        def __isub__(self, x):
            self.outer.add(self.i, -x)
        def __str__(self):
            return str(self.val)

    def __getitem__(self, i):
        if not (0 <= i < self.n): raise IndexError(i)
        return self._Element(self, i, self.sum(i, i+1))
    
    def __setitem__(self, i, x):
        if not (0 <= i < self.n): raise IndexError(i)
        if x == None: return
        self.add(i, -self.sum(i, i+1))
        self.add(i, x)
    
    def items(self):
        res, tmp = [0] * self.n, 0
        for i in range(self.n):
            s = self._sum(i+1)
            res[i] = s-tmp
            tmp = s
        return res
     
    def __str__(self):
        return "[" + ", ".join(map(str, self.items())) + "]"
    
    def _sum(self, i):
        assert 0 <= i <= self.n
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res
    
    def sum(self, i, j=None):
        if j is None: return self._sum(i)
        return self._sum(j) - self._sum(i)
    
    def add(self, i, x):
        assert 0 <= i < self.n
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def lower_bound(self, x):
        cur, s, k = 0, 0, 1 << (self.n.bit_length()-1)
        while k:
            nxt = cur + k 
            if nxt <= self.n and s + self.data[nxt] < x:
                s += self.data[nxt]
                cur = nxt
            k >>= 1
        return cur


n = int(input())
p = list(map(int, input().split()))
d = [0] * (n+1)
for i, x in enumerate(p): d[x] = i
s = SegmentTree(n)
s.build(p)
b = BIT([1] * (n+1))
ans = []

while True:
    x = s.query(0, n-1)
    if x == float("inf"): break
    i = d[x]
    ri = b.sum(i+1)
    j = b.lower_bound(ri+1)
    ans.append(x)
    ans.append(p[j])
    s.update(i, float("inf"))
    s.update(j, float("inf"))
    b[i] -= 1
    b[j] -= 1

print(*ans)
0