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 sys
import itertools

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [int(b) for b in input().split()]
    
    minmove = 1000000000
    for i in itertools.product("01", repeat = N):
        b = i
        back = 0
        Num = [None] * N
        original = dict()
        for j in range(N):
            if b[j] == "0":
                n = A[j]
            else:
                n = B[j]
                back += 1
            if n not in original: original[n] = {j}
            else: original[n] |= {j}
            Num[j] = n
        if back % 2 > 0: continue
        Num.sort() #実現したい数列
        
        appeared = set()
        move = 0
        for j, n in enumerate(Num): #このソートが実現できるか
            for o in sorted(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=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
for i in range(2**18+1):
    for j in range(n-1):
        if a!=sorted(a):
            if a[j]>a[j+1] or b[j]>b[j+1]:
                a[j+1],b[j]=b[j],a[j+1]
                a[j],b[j+1]=b[j+1],a[j]
                ans+=1
        else:
            break
        continue
    else:
        ans=-1
        break
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
prev_num = [0, 0]
curr_num = [A[0], B[0]]
for i in range(1, N):
    next_num = [A[i], B[i]]
    
    if prev_num[0] <= curr_num[0] <= next_num[0]:
        prev_num = curr_num[:]
        curr_num = next_num[:]
        continue
       
    # Flip prev and current
    if curr_num[1] <= prev_num[1]:
        prev_num, curr_num = curr_num[::-1], prev_num[::-1]
        ans += 1

    if prev_num[0] <= curr_num[0] <= next_num[0]:
        prev_num = curr_num[:]
        curr_num = next_num[:]
        continue

    # Flip current and next
    if prev_num[0] <= next_num[1]:
        curr_num, next_num = next_num[::-1], curr_num[::-1]
        ans += 1

    if prev_num[0] <= curr_num[0]:
        if i == N - 1 and curr_num[0] > next_num[0]:
            ans = -1
            break
        else:
            prev_num = curr_num[:]
            curr_num = next_num[:]
        
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
minc = 19
num = [i for i in range(N-1)]
for i in range(N-1):
    for j in combinations(num,i):
        now = 0
        flag = True
        count = len(j)
        A2 =  A.copy()
        B2 =  B.copy()
        for k in j:
            A2[k],A2[k+1],B2[k],B2[k+1] = B2[k+1],B2[k],A2[k+1],A2[k]
 
        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:
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 + (v.index(i) * 2+1))
                tmp_odd.append(odd[i])
            else:
                cnt = 0
                for j in range(N):
                    if j == i:
                        break
                    if j not in v:
                        cnt += 1
                tmp.append(even[i] * 100 + cnt * 2)
                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, odd, even)
        ans = min(ans, ans_new)

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


if __name__ == '__main__':
    main()

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 = []
        l = -1; r = 0
        for j in range(N):
            if i&(1<<j)==(1<<j):
                cur +=1
                nowA.append(B[j])
                if l==-1:
                    l = j
                r = j+1
            else:
                nowA.append(A[j])
        if cur%2==1:
            continue
        if l==-1:
            l = 0
        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:
                if candi==0 and l<=j<r:
                    candi = 2
                now +=candi
#        if (now//2)%2==(r-l)%2:
        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()


"""
4
5 2 3 4
2 8 4 2
"""

Submission status: Wrong Answer

Solution code:
from itertools import product
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
cmin = 10**3
for x in product((0,1),repeat=N):
    C = [0 for _ in range(N)]
    for i in range(N):
        if x[i]==0:
            C[i] = (A[i],i)
        else:
            C[i] = (B[i],i)
    C = sorted(C,key=lambda x:x[0])
    flag = 1
    for i in range(N):
        j = C[i][1]
        if x[j]==0:
            if i%2!=j%2:
                flag = 0
                break
        else:
            if i%2!=1-j%2:
                flag = 0
                break
    if flag==1:
        C = sorted(C,key=lambda x:x[1])
        cnt = 0
        for i in range(1,N):
            a = C[i][0]
            for j in range(i):
                if C[j][0]>a:
                    cnt += 1
        cmin = min(cmin,cnt)
if cmin <10**3:
    print(cmin)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            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,=map(int,input().split())
*b,=map(int,input().split())
m=10**18
for i in range(2**n):
    t,u=[],[]
    x=y=0
    for j in range(n):
        f=1if 2**j&i>0else 0
        if f:
            if j%2:
                t+=b[j],
            else:
                u+=b[j],
        else:
            if j%2:
                u+=a[j],
            else:
                t+=a[j],
        if j%2:
            x+=f
        else:
            y+=f
    if x!=y:
        continue
    l=[]
    for p,q in zip(sorted(t),sorted(u)):
        l+=p,
        l+=q,
    if len(t)>len(u):
        l+=max(t),
    if l!=sorted(l):
        continue
    bit=BIT(64)
    v=0
    for j,p in enumerate(t):
        bit.add(p,1)
        v+=j+1-bit.sum(p)
    bit=BIT(64)
    w=0
    for j,p in enumerate(u):
        bit.add(p,1)
        w+=j+1-bit.sum(p)
    t=(v+w)*2+max(0,v-x)+max(0,w-x)
    if w<x>v:
        t+=x-max(v,w)
    m=min(m,t)
if m==10**18:
    print(-1)
else:
    print(m)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 10**9

def count_inversion(sequence):
    return sum(sum(m < n for m in sequence[i+1:]) for i, n in enumerate(sequence))

for i in range(2**N):
    tmp = [0]*N
    count = 0
    for j in range(N):
        if (i >> j) % 2 == 1:
            tmp[j] = (A[j], j)
            count += 1
        else:
            tmp[j] = (B[j], j)

    tmp.sort()
    tmp_ans = 0
    flag = True
    tmp2 = [0]*N
    for j in range(N):
        if abs(tmp[j][1] - j) % 2 == 0:
            if tmp[j][0] != A[tmp[j][1]]:
                flag = False
                break
        else:
            if tmp[j][0] != B[tmp[j][1]]:
                flag = False
                break
    # if flag:
    #     tmp.sort(key=lambda x: x[1])
    #     tmp2 = [tmp[i][0] for i in range(N)]
    #     tmp_ans = count_inversion(tmp2)
    #     ans = min(tmp_ans, ans)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
red = list(map(int,input().split()))
blue = list(map(int,input().split()))
ans = 10 ** 5
for i in range(2 ** n):
    s = format(i,"b").zfill(n)
    num = [red[j] if s[j] == "0" else blue[j] for j in range(n)]
    num.sort()
    nu = 0
    for h in range(n):
        nu += abs(num[h]-h)
        if ((num[h]) % 101-h) % 2 != 0:
            break
        if h == n-1:
            ans = min(ans,nu//2)
if ans == 10 ** 5:
    print(-1)
else:
    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):
        one_count = bit.count(1)
        if one_count%2 == 1:
            continue

        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],x[2]))

        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: ## 可能な移動である
            if move_dist%2 == 0:
                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:
def main():

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

    if N == 1: return 0

    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())

Submission status: Wrong Answer

Solution code:
import sys
import itertools
from copy import copy

def swap(i,P,Q):
    Q[i+1],Q[i],P[i+1],P[i]=P[i],P[i+1],Q[i],Q[i+1]
    return P,Q

def judge(P):
    for i in range(len(P)-1):
        if P[i]>P[i+1]:
            return False
    else:
        return True

N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
flag=False
if judge(A):
    print(0)
    sys.exit()
for l in itertools.permutations(range(0,N-1)):
    if flag:
        break
    T=copy(A)
    Y=copy(B)
    count = 0
    for i in l:
        T,Y=swap(i,T,Y)
        count += 1
        if judge(T):
            ans = l
            flag=True
            print(count)
            break
else:
    print(-1)
    sys.exit()
#T=copy(A)
#Y=copy(B)
#print(T,Y)
#for i in ans:
#    T,Y=swap(i,T,Y)
#    print(T,Y)

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            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,=map(int,input().split())
*b,=map(int,input().split())
m=10**18
for i in range(2**n):
    t,u=[],[]
    x=y=0
    for j in range(n):
        f=1if 2**j&i>0else 0
        if f:
            if j%2:
                t+=b[j],
            else:
                u+=b[j],
        else:
            if j%2:
                u+=a[j],
            else:
                t+=a[j],
        if j%2:
            x+=f
        else:
            y+=f
    if x!=y:
        continue
    l=[]
    for p,q in zip(sorted(t),sorted(u)):
        l+=p,
        l+=q,
    if len(t)>len(u):
        l+=max(t),
    if l!=sorted(l):
        continue
    bit=BIT(64)
    v=0
    for j,p in enumerate(t):
        bit.add(p,1)
        v+=j+1-bit.sum(p)
    bit=BIT(64)
    w=0
    for j,p in enumerate(u):
        bit.add(p,1)
        w+=j+1-bit.sum(p)
    t=(v+w)*2
    if w<x>v:
        t+=x-max(v,w)
    m=min(m,t)
if m==10**18:
    print(-1)
else:
    print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
INF = 1e10
dp = [[INF] * (18) for _ in range(1<<18)]
bitcnt = [0] * (1 << 18)
dp[0][0] = 0

ans = INF

def value(ind, pos):
    if ind % 2 == pos % 2:
        return a[ind]
    else:
        return b[ind]

for i in range(1 << n):
    if i > 0:
        bitcnt[i] = bitcnt[i//2] + i%2
    for last in range(n):
        if i == (1<<n)-1:
            ans = min(ans, dp[i][last])
        if dp[i][last] == INF:
            continue
        if (not (i == 0 and last == 0)) and ((1 << last) & i) == 0:
            continue
        for nxt in range(n):
            if (1 << nxt) & i:
                continue
            if i != 0 and value(last, bitcnt[i]-1) > value(nxt, bitcnt[i]):
                continue
            nxtbit = i + (1 << nxt)
            dp[nxtbit][nxt] = min(dp[nxtbit][nxt], dp[i][last] + abs(nxt - bitcnt[i]))
    

if ans == INF:
    ans = -1
else:
    ans //= 2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
ab = []


for i in range(n):
    ab.append((aa[i], bb[i]))

min_step = 10**9
for i in range(2**n):
    bin_str = "{:020b}".format(i)[20-n:]
    bins = list(map(int, list(bin_str)))
    vals = [(ab[i][bins[i]], i, bins[i], (bins[i]+i)%2) for i in range(n)]
    
    if sum([v[3] for v in vals]) != n // 2:
        break

    step_sum = 0
    illegal = False
    evens = [v for v in vals if v[3] == 0]
    odds = [v for v in vals if v[3] == 1]

    for new_ind, (val, ht, ind, eo) in enumerate(sorted(evens)):
        new_ind = new_ind * 2
        step = abs(new_ind - ind)
        if (step % 2 == 0 and ht == 1) or (step % 2 == 1 and ht == 0):
            illegal = True
            break
        step_sum += step
    for new_ind, (val, ht, ind, eo) in enumerate(sorted(odds)):
        if illegal:
            break
        new_ind = new_ind * 2 + 1
        step = abs(new_ind - ind)
        if (step % 2 == 0 and ht == 1) or (step % 2 == 1 and ht == 0):
            illegal = True
            break
        step_sum += step
    if not illegal:
        min_step = min(min_step, step_sum//2)
if min_step == 10**9:
    print(-1)
else:
    print(min_step)

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 = []
        l = -1; r = 0
        for j in range(N):
            if i&(1<<j)==(1<<j):
                cur +=1
                nowA.append(B[j])
                if l==-1:
                    l = j
                r = j
            else:
                nowA.append(A[j])
        if cur%2==1:
            continue
        if l==-1:
            l = 0
        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:
                if candi==0 and l<=j<r:
                    candi = 2
                now +=candi
#        if (now//2)%2==(r-l)%2:
        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()


"""
4
5 2 3 4
2 8 4 2
"""

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):
        one_count = bit.count(1)
        if one_count%2 == 1:
            continue

        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: ## 可能な移動である
            if move_dist%2 == 0:
                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:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = 10**9

for i in range(1<<n):
    rev = [False for _ in range(n)]
    t = 0
    for bit in range(n):
        if i>>bit&1:
            rev[bit] = True
            t += 1
    if t%2 == 1:continue
    data_odd = []
    data_even = []
    for j in range(n):
        if rev[j]:
            if j%2 == 0:
                data_odd.append([b[j],j])
            else:
                data_even.append([b[j],j])
        else:
            if j%2 == 0:
                data_even.append([a[j],j])
            else:
                data_odd.append([a[j],j])

    if len(data_odd) != n//2:continue
    data_odd.sort()
    data_even.sort()
    q = True
    data  = []
    for j in range(n):
        if j%2 == 0:
            if  j>= 1 and data_even[j//2] < data_odd[j//2-1]:
                q = False
                break
            else:
                data.append(data_even[j//2][1])
        else:
            if j>=1 and data_odd[j//2] < data_even[(j-1)//2]:
                q = False
                break
            else:
                data.append(data_odd[j//2][1])

    if not q:continue
    res = 0
    for j in range(n-1,-1,-1):
        for k in range(j):
            if data[k] > data[k+1]:
                ponta = data[k+1]
                data[k+1] = data[k]
                data[k] = ponta
                res += 1
    ans = min(res,ans)
print(ans if ans < 10**9 else -1)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    for bit in range(1 << (N-1)):
        res = A[:]
        now = B[:]
        ans = 0
        flag = True
        for i in range(N - 1):
            if bit & (1 << i):
                ans += 1
                res[i], res[i+1], now[i], now[i+1] \
                    = now[i+1], now[i], res[i+1], res[i]
        for i in range(N-1):
            if res[i] > res[i+1]:
                flag = False
        if flag:
            return print(ans)

        res = A[:]
        now = B[:]
        ans = 0
        flag = True
        for i in range(N - 1)[::-1]:
            if bit & (1 << i):
                ans += 1
                res[i], res[i+1], now[i], now[i+1] \
                    = now[i+1], now[i], res[i+1], res[i]
        for i in range(N-1):
            if res[i] > res[i+1]:
                flag = False
        if flag:
            return print(ans)

        from collections import deque
        res = A[:]
        now = B[:]
        ans = 0
        flag = True
        k = deque(range(N - 1))
        k.rotate(3)
        for i in k:
            if bit & (1 << i):
                ans += 1
                res[i], res[i+1], now[i], now[i+1] \
                    = now[i+1], now[i], res[i+1], res[i]
        for i in range(N-1):
            if res[i] > res[i+1]:
                flag = False
        if flag:
            return print(ans)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[(x,i) for i,x in enumerate(map(int,input().split()))]
    B=[(x,i) for i,x in enumerate(map(int,input().split()))]
    l_odd,l_even=[],[]
    for i in range(N):
        if i%2:
            l_even.append(A[i])
            l_odd.append(B[i])
        else:
            l_even.append(B[i])
            l_odd.append(A[i])
    l_even.sort()
    l_odd.sort()
    stack=[]
    stack.append((0,0,[],[True]*N))
    kouho=[]
    while stack:
        n,index,l,f=stack.pop()
        if index==N:
            kouho.append(l)
            continue
        
        if index%2:
            C=l_even
        else:
            C=l_odd
        for a in C[:N-(N-index)//2]:
            if a[0]>=n and f[a[1]]:
                f2=[False]*N
                for i in range(N):
                    f2[i]=f[i]
                f2[a[1]]=False
                l2=l+[a[1]]
                stack.append((a[0],index+1,l2,f2))
    ans=INF
    if kouho:
        for l in kouho:
            c=0
            n=0
            while True:
                f=True
                for i in range(N-1):
                    if l[i]>l[i+1]:
                        l[i],l[i+1]=l[i+1],l[i]
                        c+=1
                        f=False
                if f:
                    ans=min(ans,c)
                    break
        print(ans)
    else:
        print(-1)
    
            
    
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():

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

    if all(a[0] == a[i] for i in range(n)):
        print(0)
        exit()

    pre = [1<<i for i in range(n)]
    bitcnt = [0]*(1<<n)
    bitcnt[1] = 1
    for i in range(1<<(n-1)):
        bitcnt[2*i] = bitcnt[i]
        bitcnt[2*i+1] = bitcnt[i]+1

    DP = [defaultdict(lambda : float("inf")) for i in range(n)]

    for i in range(n):
        DP[i][1<<i] = 0
    #s = defaultdict(lambda : float("inf"))
    for i in range(n-1):
        nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
        for j in range(n):
            last = a[j] if (i-j)%2 == 0 else b[j]
            for state, cost in DP[j].items():
                for to in range(n):
                    if state>>to&1:
                        continue
                    nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                    if last > nlast:
                        continue
                    nstate = state|pre[to]
                    ncost = cost
                    ncost += bitcnt[state>>to]
                    #if s[(nstate, nlast)] <= ncost:
                    #    continue
                    #s[(nstate, nlast)] = ncost
                    if nxt[to][nstate] > ncost:
                        nxt[to][nstate] = cost
        DP = nxt
    mask = (1<<n)-1
    ans = float("inf")
    for i in range(n):
        ans = min(ans, DP[i][mask])
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()