Submission #69508569

---

Source Code Expand

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def solve(N,K,X,A):
    A.sort()
    A = [a<<30 for a in A]
    def cond(x):
        cnt = 0
        t = 1
        split_done = 0
        for a in A:
            if a < x:
                continue
            while a >= 2*t*x:
                t *= 2
            cnt += 1
            split_done += t - 1
        
        if split_done >= K:
            return cnt + K >= X
        else:
            return cnt + split_done >= X and (cnt + split_done - X) + split_done >= K
        
        return cnt + min(K,split_done) >= X and split_done + cnt - X >= K

    #print(cond(1))
    ok = 0
    ng = 1<<60
    for _ in range(60):
        mid = (ok+ng)//2
        if cond(mid):
            ok = mid
        else:
            ng = mid
    
    return ok/(1<<30)

def brute(N,K,X,A):
    A.sort()
    for _ in range(K):
        a = A.pop()
        A.append(a//2)
        A.append(a//2)
        A.sort()
    return A[::-1][X-1]

while False:
    N = random.randint(1,3)
    K = random.randint(1,3)
    X = random.randint(1,N+K)
    A = [random.randint(1,10)<<30 for i in range(N)]

    N,K,X = 3,1,3
    A = [2,1,9]

    exp = brute(N,K,X,A[:])
    res = solve(N,K,X,A[:])

    if exp!=res:
        print(N,K,X)
        print([a>>30 for a in A])
        print(exp,res)
        exit()
    else:
        print("AC",N,K,X)

for _ in range(int(input())):
    N,K,X = mi()
    A = li()
    print(solve(N,K,X,A))

Submission Info

Judge Result