Submission #69631599

Source Code Expand

def f(A, M, k):
    if k == 0:
        return 0
    B = [[], []]
    for i in A:
        B[(i >> (k - 1)) & 1].append(i & ~(1 << (k - 1)))
    mid = 1 << (k - 1)
    if M == 1 << k:
        if B[0] and B[1]:
            return f(B[0], mid, k - 1) + f(B[1], mid, k - 1)
        return 2 * f(A, mid, k - 1) + mid * mid
    ans = f(B[0], min(M, mid), k - 1) if B[0] else f(A, min(M, mid), k - 1) + mid * min(M, mid)
    if M > mid:
        ans += f(B[1], M - mid, k - 1) if B[1] else f(A, M - mid, k - 1) + mid * (M - mid)
    return ans

N, M = map(int,input().split())
A = list(map(int,input().split()))
print(f(A, M, 30))

Submission Info

Submission Time
Task G - Sum of Min of XOR
User sounansya
Language Python (PyPy 3.10-v7.3.12)
Score 575
Code Size 639 Byte
Status AC
Exec Time 461 ms
Memory 142272 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 575 / 575
Status
AC × 3
AC × 45
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt, 02_random_18.txt, 02_random_19.txt, 02_random_20.txt, 02_random_21.txt, 02_random_22.txt, 02_random_23.txt, 02_random_24.txt, 02_random_25.txt, 02_random_26.txt, 02_random_27.txt, 02_random_28.txt, 02_random_29.txt, 02_random_30.txt, 02_random_31.txt, 02_random_32.txt, 02_random_33.txt, 02_random_34.txt, 02_random_35.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 55 ms 76560 KiB
00_sample_01.txt AC 55 ms 76396 KiB
00_sample_02.txt AC 56 ms 76492 KiB
01_handmade_00.txt AC 55 ms 76380 KiB
01_handmade_01.txt AC 54 ms 76492 KiB
01_handmade_02.txt AC 55 ms 76528 KiB
01_handmade_03.txt AC 55 ms 76364 KiB
01_handmade_04.txt AC 58 ms 81456 KiB
01_handmade_05.txt AC 274 ms 142192 KiB
02_random_00.txt AC 227 ms 128064 KiB
02_random_01.txt AC 260 ms 127856 KiB
02_random_02.txt AC 186 ms 128128 KiB
02_random_03.txt AC 194 ms 127848 KiB
02_random_04.txt AC 168 ms 128156 KiB
02_random_05.txt AC 104 ms 101332 KiB
02_random_06.txt AC 138 ms 94588 KiB
02_random_07.txt AC 213 ms 111280 KiB
02_random_08.txt AC 197 ms 115120 KiB
02_random_09.txt AC 180 ms 122296 KiB
02_random_10.txt AC 312 ms 127940 KiB
02_random_11.txt AC 319 ms 127868 KiB
02_random_12.txt AC 313 ms 128384 KiB
02_random_13.txt AC 302 ms 128156 KiB
02_random_14.txt AC 304 ms 127876 KiB
02_random_15.txt AC 150 ms 93664 KiB
02_random_16.txt AC 300 ms 131816 KiB
02_random_17.txt AC 280 ms 126040 KiB
02_random_18.txt AC 176 ms 101180 KiB
02_random_19.txt AC 299 ms 132652 KiB
02_random_20.txt AC 145 ms 131384 KiB
02_random_21.txt AC 148 ms 127344 KiB
02_random_22.txt AC 114 ms 128176 KiB
02_random_23.txt AC 131 ms 127172 KiB
02_random_24.txt AC 130 ms 127248 KiB
02_random_25.txt AC 113 ms 128060 KiB
02_random_26.txt AC 129 ms 128036 KiB
02_random_27.txt AC 179 ms 128156 KiB
02_random_28.txt AC 157 ms 127956 KiB
02_random_29.txt AC 156 ms 128056 KiB
02_random_30.txt AC 461 ms 141956 KiB
02_random_31.txt AC 274 ms 142272 KiB
02_random_32.txt AC 297 ms 142056 KiB
02_random_33.txt AC 262 ms 131900 KiB
02_random_34.txt AC 178 ms 132416 KiB
02_random_35.txt AC 190 ms 132168 KiB