Submission #1366740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1366740		makon	Pragmatism (KAISTRUN26SPRING_F)	Pypy 3	0 / 100	133 ms	129836 KiB

Main

import sys
from array import array
input = sys.stdin.readline

B = 30

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

    def count(lim):
        lc = array('i', [-1])
        rc = array('i', [-1])
        cnt = array('i', [0])

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

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

                cnt[v] += 1

        def query(x):
            v = 0
            ret = 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 = rc[v]
                        if t != -1:
                            ret += cnt[t]
                        v = lc[v]
                    else:
                        t = lc[v]
                        if t != -1:
                            ret += cnt[t]
                        v = rc[v]
                else:
                    if xb:
                        v = rc[v]
                    else:
                        v = lc[v]

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

            return ret

        ret = 0
        for x in a:
            ret += query(x)
            add(x)

        return ret

    l, r = 0, (1 << B) - 1

    while l < r:
        mid = (l + r) >> 1
        if count(mid) >= k:
            r = mid
        else:
            l = mid + 1

    print(l)

if __name__ == "__main__": main()

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

• Subtask 1: 0 / 20
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40