def solve_mini(N,A,Y,M=60): dp = [[1<<(M+1) for j in range(N+1)] for i in range(M+1)] for j in range(Y>>M,N+1,2): dp[M][j] = 0 low_sort = [[i for i in range(N)] for _ in range(M)] for t in range(M): low_sort[t].sort(key=lambda i:A[i]%(1<<(t+1)),reverse=True) """ pre = [i for i in range(N)] for t in range(M): zero,one = [],[] for i in pre: if A[i]>>t & 1: one.append(i) else: zero.append(i) pre = one + zero low_sort[t] = [i for i in pre] """ for i in range(M)[::-1]: zero,one,two = 0,0,0 for j in range(N): if A[j]>>i & 1: one += 1 else: zero += 1 if one&1==(Y>>i & 1): dp[i][0] = min(dp[i][0], 2*dp[i+1][two]) if (zero+two)&1==(Y>>i & 1): dp[i][0] = min(dp[i][0], 2*dp[i+1][one+two]+1) if i==0: break for j in range(1,N+1): next_up = low_sort[i-1][j-1] if A[next_up]>>i & 1: one -= 1 two += 1 else: zero -= 1 one += 1 if j!=N: next_next_up = low_sort[i-1][j] if A[next_up]%(1<<(t+1)) == A[next_next_up]%(1<<(t+1)): continue if one&1==(Y>>i & 1): dp[i][j] = min(dp[i][j], 2*dp[i+1][two]) if (zero+two)&1==(Y>>i & 1): dp[i][j] = min(dp[i][j], 2*dp[i+1][one+two]+1) if dp[0][0]==1<<(M+1): return -1 return dp[0][0] def brute(N,A,Y): ans = 2**61 def dfs(d,tmp,up): nonlocal ans if d==61: if len(up)&1==0: return tmp else: return 1<<61 res = ans if tmp > res: return ans zero,one,two = 0,set(),set() for i in range(N): if A[i]>>d & 1: if i in up: two.add(i) else: one.add(i) else: if i in up: one.add(i) else: zero += 1 if len(one)&1==(Y>>d)&1: res = min(res,dfs(d+1,tmp,two)) if (zero+len(two))&1==(Y>>d)&1 and res > tmp + (1<