結果

問題 No.3075 Mex Recurrence Formula
ユーザー Yotugi
提出日時 2025-04-08 23:48:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 442 ms / 2,000 ms
コード長 4,039 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 119,464 KB
最終ジャッジ日時 2025-04-08 23:48:33
合計ジャッジ時間 13,690 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin,setrecursionlimit#,set_int_max_str_digits
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
setrecursionlimit(20000000) # これこどふぉだと無理
#set_int_max_str_digits(200010)
mod = 998244353 
ii = lambda :int(stdin.readline())
mi = lambda :map(int,stdin.readline().split())
li = lambda :list(mi())
gmi = lambda :map(lambda x: int(x) - 1, stdin.readline().split())
gi = lambda :list(map(lambda x: 0 if x == "." else 1,input())) # グリッド入力受け取り
py = lambda :print("Yes")
pn = lambda :print("No")
pf = lambda :print("First") 
ps = lambda :print("Second")
vec = [(1,0),(-1,0),(0,-1),(0,1)]
vec1 = [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)] #8方向
inf = 2*10**18


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j = None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

    #合計値がsを超える最小のインデックス
    def lowerbound(self, s):
        x = 0
        y = 0
        for i in range(self.n.bit_length(), -1, -1):
            k = x + (1 << i)
            if k <= self.n and (y + self.data[k] < s):
                y += self.data[k]
                x += 1 << i
        return x + 1
    
    def show(self):
        ret = []
        for i in range(self.n+1):
            ret.append(self.get(i))
        print(*ret[1::])



class MexSet:
    """ 
    非負整数の追加、削除、mexの取得ができる
    n は考えられるmexの最大値をいれる(大きめにしといた方がよい)
    """
    def __init__(self,n): # ここ後で改良する
        n += 2
        self.n = n 
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)
        for i in range(1,n+1):
            while i <= self.n:
                self.data[i] += 1
                i += i & -i           

    def add(self,x,k=1):
        """
        xをk個追加(デフォルトは1個)
        """
        x += 1 
        if x > self.n:
            return 
        if self.el[x]:
            self.el[x] += k
            return 
        self.el[x] = k
        while x <= self.n:
            self.data[x] -= 1 
            x += x & -x

    def pop(self,x,k=1):
        """
        xをk個削除
        """
        x += 1 
        if x > self.n:
            return 
        assert self.el[x] >= k
        self.el[x] -= k
        if self.el[x] == 0:
            while x <= self.n:
                self.data[x] += 1 
                x += x & -x

    def pop_all(self,x):
        """
        xを全て削除
        """     
        x += 1 
        if x > self.n:
            return 
        assert self.el[x]  
        self.el[x] = 0 
        while x <= self.n:
            self.data[x] += 1 
            x += x & -x 

    def get(self,k=1):
        """
        含まれない値のうち、k番目に小さい数を返す(指定しない場合はmexを返す)
        """
        #print(self.el)
        x = 0
        y = 0
        for i in range(self.n.bit_length(), -1, -1):
            idx = x + (1 << i)
            if idx <= self.n and (y + self.data[idx] < k):
                y += self.data[k]
                x += 1 << i
        return x 
    


from collections import deque

n,x = mi() 
a = li() 
que = deque() 

ms = MexSet(n+1) 

for i in a:
    ms.add(i) 
    que.append(i) 

if n >= x:
    print(a[x-1])
    exit() 

nokori = x - n
cnt = 0 
while nokori and cnt < n+10:
    cnt += 1 
    nokori -= 1 
    v = ms.get() 
    ms.add(v)
    que.append(v) 
    a.append(v)
    ms.pop(que.popleft())

if nokori == 0:
    print(que[-1])
    exit() 

#print(a)
st = len(a) - n
a = a[-n-1:]

nokori = x - st
nokori %= len(a) 
print(a[nokori])
0