Problem:


Score : 700 points

Problem Statement

We have N cards numbered 1, 2, ..., N.
Card i (1 \leq i \leq N) has an integer A_i written in red ink on one side and an integer B_i written in blue ink on the other side.
Initially, these cards are arranged from left to right in the order from Card 1 to Card N, with the red numbers facing up.

Determine whether it is possible to have a non-decreasing sequence facing up from left to right (that is, for each i (1 \leq i \leq N - 1), the integer facing up on the (i+1)-th card from the left is not less than the integer facing up on the i-th card from the left) by repeating the operation below. If the answer is yes, find the minimum number of operations required to achieve it.

Choose an integer i (1 \leq i \leq N - 1).
Swap the i-th and (i+1)-th cards from the left, then flip these two cards.

Constraints

1 \leq N \leq 18

1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Output

If it is impossible to have a non-decreasing sequence, print -1.
If it is possible, print the minimum number of operations required to achieve it.

Sample Input 1

3
3 4 3
3 2 3

Sample Output 1

1

By doing the operation once with i = 1, we have a sequence [2, 3, 3] facing up, which is non-decreasing.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

After any number of operations, we have the sequence [2, 1] facing up, which is not non-decreasing.

Sample Input 3

4
1 2 3 4
5 6 7 8

Sample Output 3

0

No operation may be required.

Sample Input 4

5
28 15 22 43 31
20 22 43 33 32

Sample Output 4

-1

Sample Input 5

5
4 46 6 38 43
33 15 18 27 37

Sample Output 5

3



Sample input:
3
3 4 3
3 2 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ab = []

for i in range(n):
    ab.append([a[i], b[i]])

# print(ab)

def solve(idx, arr, cnt):
    if idx == n - 1:
        if arr == sorted(arr):
            return cnt
        else:
            return 10**10
    # Reverse
    new = copy.deepcopy(arr)
    new[idx][0], new[idx][1], new[idx+1][0], new[idx+1][1] = new[idx+1][1], new[idx+1][0], new[idx][1], new[idx][0]
    cnt1 = solve(idx+1, new, cnt+1)

    # Not reverse
    cnt2 = solve(idx+1, arr, cnt)

    if cnt1 < cnt2:
        return cnt1
    else:
        return cnt2

ans = solve(0, ab, 0)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from itertools import combinations
    input = sys.stdin.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    even = []
    odd = []
    for i in range(N):
        if i%2:
            odd.append(A[i])
            even.append(B[i])
        else:
            even.append(A[i])
            odd.append(B[i])

    L = list(range(N))
    ans = 10**9
    for v in combinations(L, N//2):
        ok = 1
        tmp = []
        tmp_odd = []
        tmp_even = []
        for i in range(N):
            if i in v:
                tmp.append(odd[i] * 100 + i)
                tmp_odd.append(odd[i])
            else:
                tmp.append(even[i] * 100 + i)
                tmp_even.append(even[i])

        tmp_odd.sort()
        tmp_even.sort()
        tmp_check = []
        for i in range(N):
            if i%2:
                tmp_check.append(tmp_odd[i//2])
            else:
                tmp_check.append(tmp_even[i // 2])
        for i in range(N-1):
            if tmp_check[i] > tmp_check[i+1]:
                ok = 0
                # print(v, tmp_check, odd, even)
                break
        if not ok:
            continue

        bit = Bit(5100)
        ans_new = 0
        for i in range(N-1, -1, -1):
            ans_new += bit.sum(tmp[i]-1)
            bit.add(tmp[i], 1)
        # print(v, tmp, ans_new)
        ans = min(ans, ans_new)

    if ans == 10**9:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [int(b) for b in input().split()]
    
    minmove = 1000000000
    for i in range(2 ** N):
        b = i
        back = 0
        Num = [None] * N
        original = dict()
        for j in range(N):
            if b % 2 == 0:
                Num[j] = A[j]
            else:
                Num[j] = B[j]
                back += 1
            if Num[j] not in original: original[Num[j]] = {j}
            else: original[Num[j]] |= {j}
            b //= 2
        if back % 2 > 0: continue
        Num.sort() #実現したい数列

        appeared = set()
        move = 0
        for j, n in enumerate(Num): #このソートが実現できるか
            for o in original[n]:
                if abs(j - o) % 2 == 0 and A[o] == n:
                    original[n] -= {o}
                    for key in appeared:
                        if key > o: move += 1
                    appeared |= {o}
                    break
                elif abs(j - o) % 2 == 1 and B[o] == n:
                    original[n] -= {o}
                    for key in appeared:
                        if key > o: move += 1
                    appeared |= {o}
                    break
            else: #実現できない
                break
        else: #実現できるため、操作回数を求める
            minmove = min(minmove, move)

    if minmove == 1000000000: print(-1)
    else: print(minmove)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

ans = 10**9

for i in range(2 ** n):
    j = 1
    c = []
    count = 0
    for k in range(n):
        if (i & j) == 0:
            c.append([a[k], k, 0, 0])
        else:
            c.append([b[k], k, 1, 0])
            count += 1
        j *= 2
    if count % 2 != 0:
        continue

    for _ in range(n - 1):
        for j in range(n - 1):
            if c[j] > c[j + 1]:
                c[j][-1] += 1
                c[j + 1][-1] += 1
                c[j], c[j + 1] = c[j + 1], c[j]
    

    flag = True
    for j in range(n):
        if c[j][-1] % 2 != c[j][2]:
            if j == n - 1 or c[j][0] != c[j + 1][0] or c[j+1][-1]%2==c[j+1][2]:
                flag = False
            else:
                c[j][-1] += 1
                c[j + 1][-1] += 1
                c[j], c[j + 1] = c[j + 1], c[j]

    if flag:
        cost = 0
        for j in c:
            cost += j[-1]
        ans = min(ans, cost//2)

if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

o=N//2
e=N-o

import itertools
E=[]
O=[]
for i in range(N):
    if i%2==0:
        E.append(i)
    else:
        O.append(i)
ANS=10000
for i in range(o+1):
    X=list(itertools.combinations(E,i))
    Y=list(itertools.combinations(O,i))
    for j in range(len(X)):
        for k in range(len(Y)):
            ev=[]
            od=[]
            for n in range(N):
                if n%2==0:
                    if n in X[j]:
                        od.append([B[n],n])
                    else:
                        ev.append([A[n],n])
                else:
                    if n in Y[k]:
                        ev.append([B[n],n])
                    else:
                        od.append([A[n],n])
            ev.sort()
            od.sort()
            cnt=0
            Num=0
            F=0
            for x in range(N):
                if x%2==0:
                    if Num>ev[x//2][0]:
                        F=1
                        break
                    else:
                        Num=ev[x//2][0]
                        if ev[x//2][1]>x:
                            cnt+=ev[x//2][1]-x
                else:
                    if Num>od[x//2][0]:
                        F=1
                        break
                    else:
                        Num=od[x//2][0]
                        if od[x//2][1]>x:
                            cnt+=od[x//2][1]-x
            if F==0 and ANS>cnt:
                ANS=cnt
if ANS==10000:
    print(-1)
else:
    print(ANS)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
for i in range(10000):
    for i in range(N-1):
        if A == sorted(A):
            print(ans)
            quit()
        a = A[i]
        ai = A[i+1]
        b = B[i]
        bi = B[i+1]
        if b > bi:
            if ai - a >= b - bi:
                A[i] = bi
                A[i+1] = b
                B[i] = ai
                B[i+1] = a
                ans += 1
        elif a > ai:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
print(-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]

ans = 1 << 100
for m in range(1<<N):
    C = [(A[i] if m >> i & 1 == 0 else B[i], i + (m >> i) & 1) for i in range(N)]
    CC = [(-1, 0), (-1, 0)] + sorted(C) + [(51, 0), (51, 0)]
    D = [{}, {}]
    for i in range(N):
        if CC[i+2][0] > CC[i][0]:
            D[i&1][CC[i+2][0]] = [i, i]
        if CC[i+2][0] < CC[i+4][0]:
            D[i&1][CC[i+2][0]][1] = i
    s = 0
    for i, (x, p) in enumerate(C):
        if x not in D[p]:
            break
        l, r = D[p][x]
        s += abs(i - l)
        if l == r:
            del D[p][x]
        else:
            l += 2
    else:
        ans = min(ans, s)
print(ans // 2 if ans < 1 << 100 else -1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

dp=[(0,0,0)]*n
flag=0
buf=0
count=10**9
for i in range(2**n):
    flag=0
    for j in range(n):
        if bin(i)[2:].zfill(n)[j]=='0':
            dp[j]=(a[j],j,0)
        else:
            dp[j]=(b[j],j,1)
    dp.sort()
    for j in range(n):
        if ((dp[j][1]-j)%2)!=dp[j][2]:
            flag=1
            break
    if flag==1:
        continue
    else:
        buf=0
        for j in range(n):
            if j>dp[j][1]:
                buf+=j-dp[j][1]
        count=min(count,buf)
if count==10**9:
    print(-1)
else:
    print(count)
#print(dp)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
minc = 19
for i in range(2**(N-1)):
    A2 = A.copy()
    B2 = B.copy()
    flag = True

    count = 0
    for j in range(N-1):
        if (i >> j)&1 == 1:
            count += 1
            A2[j],A2[j+1],B2[j],B2[j+1] = B2[j+1],B2[j],A2[j+1],A2[j]
    now = 0

    for j in A2:
        if now <= j:
            now = j
        else:
            flag = False
            break
    if flag:
        minc = min(minc,count)
if minc != 19:
    print(minc)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import product
N = int(input())
As = [
    list(map(int, input().split())),
    list(map(int, input().split()))
]

INF = 10000

tentou = 0
def merge_sort(array):
    global tentou
    L = len(array)
    if L == 1:
        return array
    left = merge_sort(array[:L//2])
    right = merge_sort(array[L//2:])
    array = []
    Ll = len(left)
    Lr = len(right)
    il = 0
    ir = 0
    while il < Ll and ir < Lr:
        if left[il][0] <= right[ir][0]:
            array.append(left[il])
            il += 1
        else:
            tentou += 1
            array.append(right[ir])
            ir += 1
    if il < Ll:
        array.extend(left[il:])
    if ir < Lr:
        array.extend(right[ir:])
    return array

ans = INF
for bits in product(range(2), repeat=N):
    arr = []
    for i, bit in enumerate(bits):
        arr.append((As[bit][i], i))
    tentou = 0
    arr2 = merge_sort(arr)
    d = {}
    for i, (v, j) in enumerate(arr2):
        if abs(i-j) % 2 != bits[j]:
            break
    else:
        ans = ans if ans < tentou else tentou
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
from operator import itemgetter
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()
B = inpl()

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.node = [0]*(self.size + 1)
 
    def initialize(self, S):
        # S[0] = 0にしておく
        # 1-indexed
        if len(S) < self.size + 1:
            S += [S[-1]] * (self.size+1 - len(S))
        for i in range(1, self.size+1):
            self.node[i] = S[i] - S[i - (i&-i)]
 
    def sum(self, i):
        res = 0
        while i:
            res += self.node[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.node[i] += x
            i += (i & -(i))
 
    def bisect_left(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] < x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1
 
    def bisect(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] <= x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1

ans = 10**9
g0 = itemgetter(0)
X = [(0, 0, 0) for _ in range(N)]*N
for i in range(2**N):
    I = i*1
    bit = BIT(60)
    for j in range(N):
        if I%2:
            X[j] = (A[j], j, 0)
        else:
            X[j] = (B[j], j, 1)
        I //= 2
    tmp = 0
    for j in range(N):
        bit.add(X[j][0], 1)
        tmp += j + 1 - bit.sum(X[j][0])
    X = sorted(X, key=g0)
    l = 0
    r = 0
    while l < N:
        for r in range(l, N):
            if X[l][0] != X[r][0]:
                break
        else:
            r = N
        p = 0
        for x in range(l, r-1):
            if abs(x - X[x][1] + p)%2 != X[x][2]:
                tmp += 1
                p = 1
            else:
                p = 0
        x = r-1
        if abs(x - X[x][1] + p)%2 != X[x][2]:
            tmp = 10**9
            break
        l = r
    ans = min(tmp, ans)
if (ans == 10**9):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from itertools import combinations
    input = sys.stdin.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    even = []
    odd = []
    for i in range(N):
        if i%2:
            odd.append(A[i])
            even.append(B[i])
        else:
            even.append(A[i])
            odd.append(B[i])

    L = list(range(N))
    ans = 10**9
    for v in combinations(L, N//2):
        ok = 1
        tmp = []
        tmp_odd = []
        tmp_even = []
        for i in range(N):
            if i in v:
                tmp.append(odd[i])
                tmp_odd.append(odd[i])
            else:
                tmp.append(even[i])
                tmp_even.append(even[i])

        tmp_odd.sort()
        tmp_even.sort()
        tmp_check = []
        for i in range(N):
            if i%2:
                tmp_check.append(tmp_odd[i//2])
            else:
                tmp_check.append(tmp_even[i // 2])
        for i in range(N-1):
            if tmp_check[i] > tmp_check[i+1]:
                ok = 0
                # print(v, tmp_check, odd, even)
                break
        if not ok:
            continue

        bit = Bit(51)
        ans_new = 0
        for i in range(N-1, -1, -1):
            ans_new += bit.sum(tmp[i]-1)
            bit.add(tmp[i], 1)
        # print(v, tmp, ans_new)
        ans = min(ans, ans_new)

    if ans == 10**9:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,time
input = sys.stdin.readline

def main():
    pti = time.time()
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    dg = 10**7

    dp = [[10**5]*n for i in range(2**n)]

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s][i] = i
        new.add(s*dg+i)
    

    for k in range(n-1):
        tank = set([])
        if len(new) == 0:
            break
        for popelt in new:
            s,idx = popelt//dg,popelt%dg
            if (k-idx)%2 == 0:
                fr = a[idx]
            else:
                fr = b[idx]
            cnt = 0
            for j in range(n):
                if (s>>j)&1 == 0:
                    if (j-k)%2 == 1:
                        val = a[j]
                    else:
                        val = b[j]
                    if val >= fr and dp[s+(1<<j)][j] > dp[s][idx]+j-cnt:
                        dp[s+(1<<j)][j] = dp[s][idx]+j-cnt
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
        if time.time()-pti > 1.5:
            print(-1)
            return   
        new = tank
    
    res = min(dp[2**n-1])

    if res == 10**5:
        print(-1)
    else:
        print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
flag = False
ans = 0
count = 0
while True:
    if count == 10**5:
        ans = -1
        break
    for i in range(1,N):
        if A[i-1] > A[i]:
            break
        if i == N-1:
            flag = True
    if flag:
        break
    for i in range(1,N):
        if B[i-1] > B[i] or A[i-1] > A[i]:
            tmpA = [A[i-1],A[i]]
            tmpB = [B[i-1],B[i]]
            A[i-1],A[i] = tmpB[1],tmpB[0]
            B[i-1],B[i] = tmpA[1],tmpA[0]
            ans += 1
    count += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
IAB = [(i, A[i], B[i]) for i in range(N)]

ans = 10**9
pos_0 = 0b101010101010101010
for color in range(2**N):
    C = [b if (color>>i)&1 else a for i,a,b in IAB]
    pos_1 = color ^ pos_0
    P = [(pos_1>>i)&1 for i in range(N)]

    C_sorted = sorted(C)

    n_operation = 0
    for i in range(N):
        found = False
        for j in range(i, N):
            if C[j]==C_sorted[i] and P[j]==i&1:
                found = True
                break

        if found:
            n_operation += j-i
            for j in range(j, i, -1):
                C[j], C[j-1] = C[j-1], C[j]
                P[j], P[j-1] = P[j-1], P[j]
        else:
            break
                
    if found:
        ans = min(ans, n_operation)
    
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]

odd_bit = 0b0101010101010101010101
eve_bit = 0b1010101010101010101010
full_bit = 2**n - 1

odd_num = (n + 1) // 2
ans = 10**9 

for i in range(2**n):
    invi = full_bit ^ i
    odd = bin(i & odd_bit).count("1") + bin(invi & eve_bit).count("1")
    if odd != odd_num:
        continue
    odd_card = []
    eve_card = []
    for j in range(n):
        if i & 1 << j:
            if j % 2 == 0:
                odd_card.append((a[j], j))
            else:
                eve_card.append((a[j], j))
        else:
            if j % 2 == 1:
                odd_card.append((b[j], j))
            else:
                eve_card.append((b[j], j))
    odd_card.sort()
    eve_card.sort()
    odd_itr = 0
    eve_itr = 0
    curr = 0
    val = 0
    ok = True
    for i in range(n):
        if i % 2 == 0:
            num, index = odd_card[odd_itr]
            val += abs(index - i)
            odd_itr += 1
        else:
            num, index = eve_card[eve_itr]
            val += abs(index - i)
            eve_itr += 1
        if num < curr:
            ok = False
            break
        curr = num
    if ok:
        ans = min(ans, val)

if ans == 10**9:
    print(-1)
else:
    print(ans // 2)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
import time
import copy
start = time.time()
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
X = []
for i in range(N):
    X.append((A[i],B[i]))
ans = -1
Q = [(0,X)]
while Q:
    if time.time()-start>1.6:break
    q = heappop(Q)
    A = [e[0] for e in q[1]]
    if A==sorted(A):
        ans=max(q[0],ans)
        break
    for i in range(N-1):
        Y = q[1][:]
        Y[i] = (q[1][i+1][1],q[1][i+1][0])
        Y[i+1] = (q[1][i][1],q[1][i][0])
        heappush(Q,(q[0]+1,Y))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
for i in range(10000):
    for i in range(N-1):
        if A == sorted(A):
            print(ans)
            quit()
        a = A[i]
        ai = A[i+1]
        b = B[i]
        bi = B[i+1]
        if b > bi:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
            continue
        elif a > ai:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
            continue
print(-1)

Submission status: Wrong Answer

Solution code:
def examA():
    H = I()
    W = I()
    N = I()
    ans = (N-1)//max(H,W) + 1
    print(ans)
    return

def examB():
    N = I()
    XL = [LI()for _ in range(N)]
    for i in range(N):
        XL[i][0] += XL[i][1]
    XL.sort()
#    print(XL)
    ans = 0
    now = -inf
    for i in range(N):
        if XL[i][0]-XL[i][1]*2>=now:
            ans +=1
            now = XL[i][0]
    print(ans)
    return

def examC():
    N, K, S = LI()
    A = [0]*N
    if S>=10**6:
        a = 1
    else:
        a = S+1
    for i in range(N):
        if i<K:
            A[i] = S
        else:
            A[i] = a
    print(" ".join(map(str,A)))
    return

def examD():
    N = I()
    A = LI()
    B = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cur = 0
        nowA = []
        for j in range(N):
            if i&(1<<j)==(1<<j):
                cur +=1
                nowA.append(B[j])
            else:
                nowA.append(A[j])
        if cur%2==1:
            continue
        pr = sorted(nowA)
#        print(nowA,pr)
        now = 0
        for j in range(N):
            dist = [i for i, x in enumerate(pr) if x == nowA[j]]
#            print(dist)
            candi = inf
            for v in dist:
                if ((abs(v-j)%2)==1 and i&(1<<j)==(1<<j)):
                    candi = min(candi,abs(v-j))
                if ((abs(v-j)%2)==0 and i&(1<<j)==0):
                    candi = min(candi,abs(v-j))
            if candi==inf:
#                print(dist, i & (1 << j),i,j)
                now = inf
                break
            else:
                now +=candi
        ans = min(ans,now)
#        print(now)
    if ans==inf:
        print(-1)
    else:
        print(ans//2)
    return

def examE():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]

L = [[0]*2 for _ in range(N)]

for i in range(N):
    L[i][i%2] = A[i]
    L[i][(i+1)%2] = B[i]

P = [int(i) for i in range(N)]

ans = 10**10
import itertools
for C in itertools.combinations(P, (N+1)//2):
    C = list(C)
    used = [0]*N
    for i in C:
        used[i] = 1
    B_temp = []
    for i in range(N):
        if used[i] == 0:
            B_temp.append((L[i][1], i))
            
    temp = [0]*N
    check = [0]*N
    B_temp.sort()
    for i in range(len(C)):
        C[i] = (L[C[i]][0], C[i])
    C.sort()
    j = 0
    k = 0
    for i in range(N):
        if i%2 == 0:
            temp[i] = C[j][1]
            check[i] = C[j][0]
            j += 1
        else:
            temp[i] = B_temp[k][1]
            check[i] = B_temp[k][0]
            k += 1
    if check != sorted(check):
        continue

    cnt = 0
    j = N-1
    for i in range(N-1, -1, -1):
        idx = temp.index(i)
        if idx == j:
            j -= 1
            continue
        cnt += j-idx
        temp[idx] = temp[j]
        temp[j] = j
        j -= 1
    ans = min(ans, cnt)

if ans == 10**10:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product

def solve(N: int, A: "List[int]", B: "List[int]"):
    AB = list(zip(A,B))
    answer = 10**18
    #0が表,1が裏返す
    for bit in product([0,1],repeat=N):
        num_list = []
        #(数字,表か裏か,元々のindex)
        for i in range(N):
            num_list.append((AB[i][bit[i]],bit[i],i))
        num_list.sort(key=lambda x: x[0])

        move_dist = 0
        for i in range(N):
            _, flag, index = num_list[i]

            if abs(i-index)%2 != flag:
                break

            move_dist += abs(i-index)
        else: ## 可能な移動である
            answer = min(answer,move_dist//2)
    if answer == 10**18:
        print(-1)
    else:
        print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
from operator import itemgetter
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()
B = inpl()

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.node = [0]*(self.size + 1)
 
    def initialize(self, S):
        # S[0] = 0にしておく
        # 1-indexed
        if len(S) < self.size + 1:
            S += [S[-1]] * (self.size+1 - len(S))
        for i in range(1, self.size+1):
            self.node[i] = S[i] - S[i - (i&-i)]
 
    def sum(self, i):
        res = 0
        while i:
            res += self.node[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.node[i] += x
            i += (i & -(i))
 
    def bisect_left(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] < x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1
 
    def bisect(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] <= x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1

ans = 10**9
g0 = itemgetter(0)
for i in range(2**N):
    X = []
    I = i*1
    for j in range(N):
        C = Counter()
        bit = BIT(60)
        if I%2:
            X.append((A[j], j, 0))
            C[A[j]] += 1
        else:
            X.append((B[j], j, 1))
            C[B[j]] += 1
        I //= 2

    tmp = 0
    for j in range(N):
        bit.add(X[j][0], 1)
        tmp += j + 1 - bit.sum(X[j][0])
    X = sorted(X, key=g0)
    l = 0
    r = 0
    while l < N:
        for r in range(l, N):
            if X[l][0] != X[r][0]:
                break
        else:
            r = N
        p = 0
        for x in range(l, r-1):
            if abs(x - X[x][1] + p)%2 != X[x][2]:
                tmp += 1
                p = 1
            else:
                p = 0
        x = r-1
        if abs(x - X[x][1] + p)%2 != X[x][2]:
            tmp = 10**9
            break
        l = r
    ans = min(tmp, ans)
if (ans == 10**9):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():

    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    cur = -1
    for i in range(N):
        if A[i] >= cur or B[i] >= cur:
            cur = min(A[i], B[i])
        else:
            return -1

    hash = [0]
    for i in range(N-1):
        temp = []
        for h in hash:
            temp.append(h | (1 << i))
            temp.append(h)
        hash = temp

    ans = float('inf')
    for h in hash:
        flip = [0 for _ in range(N)]
        pos = []
        cur = 0
        for i in range(N-1):
            if (h >> i) % 2 == 1:
                flip[i+1] += 1
                flip[cur] += 1
                pos.append(i+1)
            else:
                pos.append(cur)
                cur = i+1
        pos.append(cur)
        # print(flip)

        val = [-1]
        isfound = True
        for i in range(N):
            if flip[pos[i]] % 2 == 0:
                v = A[pos[i]]
            else:
                v = B[pos[i]]
            if val[-1] <= v:
                val.append(v)
            else:
                isfound = False
                break
        if isfound:
            # print(flip, val)
            ans = min(ans, sum(flip)//2)

    if ans == float('inf'):
        return -1
    return ans

if __name__ == '__main__':
    print(main())