Submission #1366735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1366735		makon	Kirameki of Revue (KAISTRUN26SPRING_E)	Pypy 3	40 / 100	4584 ms	2162688 KiB

Main

import sys
input = sys.stdin.readline

B = 30

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    lch = [-1]
    rch = [-1]
    cnt = [0]

    def add(x):
        v = 0
        cnt[v] += 1

        for b in range(B - 1, -1, -1):
            if (x >> b) & 1:
                nv = rch[v]
                if nv == -1:
                    nv = len(cnt)
                    rch[v] = nv
                    lch.append(-1)
                    rch.append(-1)
                    cnt.append(0)
                v = nv
            else:
                nv = lch[v]
                if nv == -1:
                    nv = len(cnt)
                    lch[v] = nv
                    lch.append(-1)
                    rch.append(-1)
                    cnt.append(0)
                v = nv

            cnt[v] += 1

    def query(x, lim):
        v = 0
        res = 0

        for b in range(B - 1, -1, -1):
            if v == -1:
                break

            xb = (x >> b) & 1
            lb = (lim >> b) & 1

            if lb:
                if xb:
                    t = rch[v]
                    if t != -1:
                        res += cnt[t]
                    v = lch[v]
                else:
                    t = lch[v]
                    if t != -1:
                        res += cnt[t]
                    v = rch[v]
            else:
                if xb:
                    v = rch[v]
                else:
                    v = lch[v]

        if v != -1:
            res += cnt[v]

        return res

    def count(lim):
        lch[:] = [-1]
        rch[:] = [-1]
        cnt[:] = [0]

        res = 0
        for x in a:
            res += query(x, lim)
            add(x)

        return res

    lo, hi = 0, (1 << B) - 1

    while lo < hi:
        mid = (lo + hi) // 2
        if count(mid) >= k:
            hi = mid
        else:
            lo = mid + 1

    print(lo)

if __name__ == "__main__": main()

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 46%)

=======

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 35 / 35
• Subtask 4: 0 / 40