Submission #66386065


Source Code Expand

def _echelonize(a: list[int]):
    for i in range(len(a)):
        for j in range(i):
            a[i] = min(a[i], a[i] ^ a[j])
        for j in range(i):
            a[j] = min(a[j], a[i] ^ a[j])

def solve_all(a: list[int], inbits: int):
    a = a[:]
    _echelonize(a)
    free = (1 << inbits+1) - 1
    for v in a:
        if v == 0:
            continue
        free ^= 1 << v.bit_length()-1
    if not (free & 1):
        return
    x = free
    while True:
        y = x
        for v in a:
            if (v & y).bit_count() & 1:
                y ^= 1 << v.bit_length()-1
        yield y >> 1
        if x == 1:
            break
        x = (x - 2) & free

def solve(n, k, a):
    use = [0] * 60
    for j in range(60):
        for i in range(n):
            use[j] ^= (a[i] >> j & 1) << (i + 1)
        use[j] ^= k >> j & 1
    for b in solve_all(use, n):
        b = [b>>i&1 for i in range(n)]
        ans = []
        def merge_right(i, to, ans):
            if b[i] == 0:
                ans += [i+1, i+1, i+2, i+1]
            else:
                ans += [i+1]
                for j in range(i+2, to+1):
                    ans += [j, j, j-1, j]
        def merge_left(i, ans):
            if b[i] == 0:
                ans += [i, i, i-1, i]
            else:
                ans += [i]
                for j in range(i-2, -1, -1):
                    ans += [j+1, j+1, j+2, j+1]
        found = False
        if all(b[i] == 0 for i in range(n)):
            ans += [1, 1]
            found = True
        else:
            for i in range(1, n):
                if b[i-1] == b[i]:
                    found = True
                    if b[i] == 0 and i > 1 and b[i-2] == 1:
                        ans += [i, i, i-1, i]
                        for j in reversed(range(0, i-2)):
                            merge_right(j, i, ans)
                        for j in range(i+1, n):
                            merge_left(j, ans)
                        break
                    elif b[i] == 0 and i+1<n and b[i+1] == 1:
                        ans += [i, i, i+1, i]
                        for j in reversed(range(0, i-1)):
                            merge_right(j, i+1, ans)
                        for j in range(i+2, n):
                            merge_left(j, ans)
                        break
                    elif b[i]==1:
                        ans += [i]
                        for j in reversed(range(0, i-1)):
                            merge_right(j, i, ans)
                        for j in range(i+1, n):
                            merge_left(j, ans)
                        break
                    found = False
        if found:
            return ans
    return None

def check(n, k, a, op):
    a = a[:]
    for i in op:
        x = a[i-1] ^ a[i]
        a[i-1] = a[i] = x
    return a[0] == k

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    res = solve(n, k, a)
    if res:
        print("Yes")
        print(len(res))
        print(*res)
        assert check(n, k, a, res)
    else:
        print("No")

Submission Info

Submission Time
Task B - Adjacent Replace
User Yu_212
Language Python (PyPy 3.10-v7.3.12)
Score 800
Code Size 3223 Byte
Status AC
Exec Time 104 ms
Memory 84632 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 1
AC × 34
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 63 ms 81224 KiB
01_test_00.txt AC 71 ms 81660 KiB
01_test_01.txt AC 79 ms 82656 KiB
01_test_02.txt AC 91 ms 83848 KiB
01_test_03.txt AC 90 ms 83384 KiB
01_test_04.txt AC 104 ms 84408 KiB
01_test_05.txt AC 97 ms 83996 KiB
01_test_06.txt AC 98 ms 83812 KiB
01_test_07.txt AC 99 ms 84316 KiB
01_test_08.txt AC 80 ms 82816 KiB
01_test_09.txt AC 91 ms 83592 KiB
01_test_10.txt AC 104 ms 83716 KiB
01_test_11.txt AC 99 ms 83992 KiB
01_test_12.txt AC 98 ms 83652 KiB
01_test_13.txt AC 83 ms 83072 KiB
01_test_14.txt AC 93 ms 83688 KiB
01_test_15.txt AC 94 ms 84176 KiB
01_test_16.txt AC 102 ms 84632 KiB
01_test_17.txt AC 102 ms 83932 KiB
01_test_18.txt AC 103 ms 84136 KiB
01_test_19.txt AC 103 ms 84268 KiB
01_test_20.txt AC 89 ms 83580 KiB
01_test_21.txt AC 86 ms 83408 KiB
01_test_22.txt AC 95 ms 83656 KiB
01_test_23.txt AC 95 ms 83728 KiB
01_test_24.txt AC 75 ms 81872 KiB
01_test_25.txt AC 79 ms 82872 KiB
01_test_26.txt AC 85 ms 83768 KiB
01_test_27.txt AC 77 ms 82704 KiB
01_test_28.txt AC 76 ms 82672 KiB
01_test_29.txt AC 83 ms 83224 KiB
01_test_30.txt AC 87 ms 83572 KiB
01_test_31.txt AC 81 ms 83068 KiB
01_test_32.txt AC 103 ms 84020 KiB