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 numpy.random as random
import copy

def issorted(x):
    
    size = len(x)
    for i in range(size-1):
        if x[i] > x[i+1]:
            return False
    return True

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

ans = 9999999
flag = False
for i in range(10**4):
    a = copy.copy(A)
    b = copy.copy(B)
    t = 0
    
    for j in range(10**2):
        if issorted(a):
            # print(a,b)
            flag = True
            break
        k = random.randint(0,N-1)
        a[k],b[k+1] = b[k+1],a[k]
        a[k+1],b[k] = b[k],a[k+1]
        t += 1
    if ans > t:
        ans = t

if flag == False:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy.random as random
import copy

def issorted(x):
    
    size = len(x)
    for i in range(size-1):
        if x[i] > x[i+1]:
            return False
    return True

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

ans = 9999999
flag = False
for i in range(10**3):
    a = copy.copy(A)
    b = copy.copy(B)
    t = 0
    
    for j in range(10**3):
        if issorted(a):
            # print(a,b)
            flag = True
            break
        k = random.randint(0,N-1)
        a[k],b[k+1] = b[k+1],a[k]
        a[k+1],b[k] = b[k],a[k+1]
        t += 1
    if ans > t:
        ans = t

if flag == False:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0 for _ in range(n+1)]
    def sum(self,index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res
    def add(self,index,x): #1-index
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

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

ans = 10**18

for i in range(2**N):
    C = []
    bcount = 0
    for j in range(N):
        if ((i >> j) & 1):
            C.append([A[j],j,0])
        else:
            C.append([B[j],j,1])
            bcount += 1
    if bcount %2 != 0:
        continue
        
    C.sort()

    check = True
    for i in range(N):
        if (C[i][1]+C[i][2])%2 != i%2:
            if i != N-1 and C[i][0] == C[i+1][0] and(C[i+1][1]+C[i+1][2])%2 == i%2:
                C[i][0],C[i+1][0] = C[i+1][0],C[i][0]
                C[i][1],C[i+1][1] = C[i+1][1],C[i][1]
                C[i][2],C[i+1][2] = C[i+1][2],C[i][2]
            else:
                check = False
                break
    if not check:
        continue
    else:
        count = 0
        bit = BinaryIndexedTree(N+1)

        for k in range(N):
            bit.add(C[k][1]+1,1)
            count += k+1-bit.sum(C[k][1]+1)

        ans = min(ans,count)

print(ans if ans != 10**18 else -1)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import math

def first(i,a,b):
    if i%2==0: return [a,b,i]
    else: return [b,a,i]

def chk(a,b):
    if n%2==0:
        for i in range(m-1):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0
        if a[m-1][0]>b[m-1][0]: return 0
            
    else:
        for i in range(m-1):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0

    return 1

def cal(a,b):
    l=[]
    if n%2==0:
        for i in range(m):
            l+=[a[i][1],b[i][1]]
    if n%2==1:
        for i in range(m-1):
            l+=[a[i][1],b[i][1]]
        l.append(a[m-1][1])
    return l
        


n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if n==1:
    print(0)
    sys.exit()

x=[first(i,a[i],b[i]) for i in range(n)]
x.sort()


m=math.ceil(n/2)
p=[i for i in range(n)]
ans=1000000

for q in list(itertools.combinations(p,m)):
    tmpa,tmpb=[],[]
    for i in range(n):
        if i in q: tmpa.append([ x[i][0],x[i][2] ])
        else: tmpb.append([x[i][1],x[i][2]])
    tmpb.sort()


    if chk(tmpa,tmpb)==1:
        s=[0 for i in range(n)]
        t=cal(tmpa,tmpb)
        tans=0
        for i in range(n-1):
            for j in range(i+1,n):
                if a[i]>a[j]: tans+=1
        ans=min(ans,tans)

print(ans if ans<1000000 else -1)

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(2**N):
    cand = 0
    i = bin(i)[2:]
    i = '0'*(N-len(i))+i
    l = []
    for j in range(N):
        if i[j]=='0':
            l.append([A[j],j])
        else:
            l.append([B[j],j])
    for j in range(N):
        for k in range(j+1,N):
            if l[j][0]>l[k][0]:
                cand += 1
    pos = True
    for j in range(N):
        if (l[j][1]-j)%2==0 and i[l[j][1]]=='0':
            continue
        if (l[j][1]-j)%2==1 and i[l[j][1]]=='1':
            continue
        else:
            if j==N-1:
                pos = False
                break
            if (l[j+1][1]-j-1)%2==0 and i[l[j+1][1]]=='1':
                cand += 1
                l[j],l[j+1]=l[j+1],l[j]
                continue
            if (l[j+1][1]-j-1)%2==1 and i[l[j+1][1]]=='0':
                cand += 1
                l[j],l[j+1]=l[j+1],l[j]
                continue
            if j==N-2:
                pos = False
                break
            if (l[j+2][1]-j-2)%2==0 and i[l[j+2][1]]=='0':
                cand += 2
                l[j],l[j+1],l[j+2]=l[j+2],l[j],l[j+1]
                continue
            if (l[j+2][1]-j-2)%2==0 and i[l[j+2][1]]=='1':
                cand += 2
                l[j],l[j+1],l[j+2]=l[j+2],l[j],l[j+1]
                continue
            pos = False
            break
    if pos:
        ans = min(ans,cand)

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

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0 for _ in range(n+1)]
    def sum(self,index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res
    def add(self,index,x): #1-index
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

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

ans = 10**18

for i in range(2**N):
    C = []
    for j in range(N):
        if ((i >> j) & 1):
            C.append([A[j],j,0])
        else:
            C.append([B[j],j,1])
    C.sort()

    check = True
    for i in range(N):
        if (C[i][1]+C[i][2])%2 != i%2:
            if i != N-1 and C[i][0] == C[i+1][0] and(C[i+1][1]+C[i+1][2])%2 == i%2:
                C[i][0],C[i+1][0] = C[i+1][0],C[i][0]
                C[i][1],C[i+1][1] = C[i+1][1],C[i][1]
                C[i][2],C[i+1][2] = C[i+1][2],C[i][2]
            else:
                check = False
                break
    if not check:
        continue
    else:
        count = 0
        bit = BinaryIndexedTree(N+1)
        
        for k in range(N):
            bit.add(C[k][1]+1,1)
            count += k+1-bit.sum(C[k][1]+1)
            
        ans = min(ans,count)

print(ans if ans != 10**18 else -1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import combinations

n = int(input())
rs = np.array(list(map(int, input().split())))
bs = np.array(list(map(int, input().split())))
_rs = np.array([rs[i] if i %2 == 0 else bs[i] for i in range(n)])
_bs = np.array([rs[i] if i %2 ==1 else bs[i] for i in range(n)])
rs=_rs
bs=_bs
c = [(r, s, i) for i, (r, s) in enumerate(zip(rs, bs))]

h = n // 2
if n % 2:
    h += 1
all_ = np.arange(n)
MAX=10000
res = MAX
for al in combinations(range(n), h):
    idx = np.full(n, False, dtype=bool)
    idx[list(al)] = True

    rl = sorted([(r, i) for r, i in zip(rs[idx], al)])
    bl = sorted([(b,i) for b, i in zip(bs[~idx], all_[~idx])])
    v = []
    for i in range(0, n):
        if i % 2:
            v.append(bl.pop(0))
        else:
            v.append(rl.pop(0))
    l = 0
    buf = -100
    ok=True
    for i,vv in enumerate(v):
        l += abs(i - vv[1])
        if buf > vv[0]:
            ok=False
            break
        buf = vv[0]
    if ok:
        res = min(res, l//2)
    
if res == MAX:
    print(-1)
else:
    print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

def select(d, index_list, list_min):
    while True:
        uo = len(index_list)%2
        index = np.argmin(d[uo])
        if d[uo][index] == 100:
            if len(d[0]) == len(index_list):
                return index_list
            else:
                return -1
        if list_min > d[uo][index]:
            d[uo][index] = 100
            continue
        tmp = d[(uo+1)%2][index]
        list_min_tmp = d[uo][index]
        d[0][index], d[1][index] = 100, 100
        ret = select(d, index_list + [index], list_min_tmp)

        if ret != -1:
            break
        else:
            d[(uo+1)%2][index] = tmp
    return ret
        

(n,),*d = [list(map(int, s.split())) for s in open(0)]

for i in range(1, n, 2):
    d[0][i], d[1][i] = d[1][i], d[0][i]
d = np.array(d)

index_list = []
list_min = 0
index = np.argmin(d[0])

ret = select(d, index_list, list_min)

if ret == -1:
    print(ret)
else:
    ans = 0
    for i in range(len(ret)):
        for j in range(i, len(ret)):
            if ret[i] > ret[j]:
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
I=0
flag=0
Sa=copy.deepcopy(a)
Sb=copy.deepcopy(b)
anslist=[]
jh=[0]
def play(ca,cb,I,lis):
  if I==n-1:
    anslist.append([ca,lis])
    return
  else:
    sa=copy.deepcopy(ca)
    sb=copy.deepcopy(cb)
    ll=lis+[0]
    play(sa,sb,I+1,ll)
    ls=lis+[1]
    ta=copy.deepcopy(ca)
    tb=copy.deepcopy(cb)
    s,t=sa[I],sb[I]
    ta[I],tb[I]=sb[I+1],sa[I+1]
    tb[I+1],ta[I+1]=s,t
    play(ta,tb,I+1,ls)
play(Sa,Sb,0,jh)
kai=18
for i in range(len(anslist)):
  if sorted(anslist[i][0])==anslist[i][0]:
    flag=1
    z=sum(anslist[i][1])
    if kai>z:
      kai=z
if flag==0:
  print(-1)
else:
  print(kai)

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0 for _ in range(n+1)]
    def sum(self,index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res
    def add(self,index,x): #1-index
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

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

ans = 10**18

for i in range(2**N):
    count = 0
    bit = BinaryIndexedTree(N+1)
    C = []
    for j in range(N):
        if ((i >> j) & 1):
            C.append([A[j],j,0])
        else:
            C.append([B[j],j,1])
    C.sort()

    check = True
    for i in range(N):
        if (C[i][1]+C[i][2])%2 != i%2:
            if i != N-1 and C[i][0] == C[i+1][0] and(C[i+1][1]+C[i+1][2])%2 == i%2:
                C[i][0],C[i+1][0] = C[i+1][0],C[i][0]
                C[i][1],C[i+1][1] = C[i+1][1],C[i][1]
                C[i][2],C[i+1][2] = C[i+1][2],C[i][2]
            else:
                check = False
                break
    if not check:
        continue
    else:
        for k in range(N):
            bit.add(C[k][1]+1,1)
            count += k+1-bit.sum(C[k][1]+1)
        ans = min(ans,count)

print(ans if ans != 10**18 else -1)

Submission status: Wrong Answer

Solution code:
import numpy as np

def select(d, index_list, list_min):
    while True:
        uo = len(index_list)%2
        index = np.argmin(d[uo])
        if d[uo][index] == 100:
            if len(d[0]) == len(index_list):
                return index_list
            else:
                return -1
        if list_min > d[uo][index]:
            d[uo][index] = 100
            continue
        tmp = d[-uo-1][index]
        d[0][index], d[1][index] = 100, 100
        ret = select(d, index_list + [index], d[uo][index])

        if ret != -1:
            break
        else:
            d[-uo-1][index] = tmp
    return ret
        

(n,),*d = [list(map(int, s.split())) for s in open(0)]

for i in range(1, n, 2):
    d[0][i], d[1][i] = d[1][i], d[0][i]
d = np.array(d)

index_list = []
list_min = 0
index = np.argmin(d[0])

ret = select(d, index_list, list_min)

if ret == -1:
    print(ret)
else:
    ans = 0
    for i in range(len(ret)):
        for j in range(i, len(ret)):
            if ret[i] > ret[j]:
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
I=0
flag=0
Sa=copy.deepcopy(a)
Sb=copy.deepcopy(b)
anslist=[]
jh=[0]
def play(ca,cb,I,lis):
  if I==n-1:
    anslist.append([ca,lis])
    return
  else:
    sa=copy.deepcopy(ca)
    sb=copy.deepcopy(cb)
    ll=lis+[0]
    play(sa,sb,I+1,ll)
    ls=lis+[1]
    ta=copy.deepcopy(ca)
    tb=copy.deepcopy(cb)
    s,t=sa[I],sb[I]
    ta[I],tb[I]=sb[I+1],sa[I+1]
    tb[I+1],ta[I+1]=s,t
    play(ta,tb,I+1,ls)
play(Sa,Sb,0,jh)
kai=18
for i in range(len(anslist)):
  if sorted(anslist[i][0])==anslist[i][0]:
    flag=1
    if kai>sum(anslist[i][1]):
      kai=sum(anslist[i][1])
if flag==0:
  print(-1)
else:
  print(kai)

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)

        else:
            tmp[j] = (B[j], j)
            count += 1
    if count % 2 == 1:
        continue
    tmp.sort()
    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:
import copy
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
I=0
flag=0
Sa=copy.deepcopy(a)
Sb=copy.deepcopy(b)
anslist=[]
jh=[0]
def play(ca,cb,I,lis):
  if I==n-1:
    anslist.append([ca,lis])
    return
  else:
    sa=copy.deepcopy(ca)
    sb=copy.deepcopy(cb)
    ll=lis+[0]
    play(sa,sb,I+1,ll)
    ls=lis+[1]
    ta=copy.deepcopy(ca)
    tb=copy.deepcopy(cb)
    s,t=sa[I],sb[I]
    ta[I],tb[I]=sb[I+1],sa[I+1]
    tb[I+1],ta[I+1]=s,t
    play(ta,tb,I+1,ls)
play(Sa,Sb,0,jh)
for i in range(len(anslist)):
  if sorted(anslist[i][0])==anslist[i][0]:
    flag=1
    kai=anslist[i][1]
if flag==0:
  print(-1)
else:
  print(sum(kai))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 10 ** 18
for i in range(2 ** n):
  s = []
  t = 0
  for j in range(n):
    if ((i >> j) & 1):
      s.append((b[j],j,1))
      t += 1
    else:
      s.append((a[j],j,0))
  if t % 2:
    continue
  bucket = [list() for i in range(51)]
  for v,k,e in s:
    bucket[v].append((k,e))
  now = 0
  ans2 = 0
  for j in bucket[1:]:
    c = 0
    ke = 0
    for k,e in j:
      if (k+e-now) % 2:
        if c:
          c = 0
          ans2 += (abs(k - ke[0]) + abs(now-ke[1])) 
          ke = 0
        else:
          c = 1
          ke = (now,k)
      else:
        ans2 += abs(k-now) 
      now += 1
    else:
      if c:
        break
  else:
    ans = min(ans,ans2//2)
if ans == 10 ** 18:
  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()))

X = [(A[i], i) for i in range(N)]
Y = [(B[i], i) for i in range(N)]


def change(i, j):
    A[i], B[i], A[j], B[j] = B[j], A[j], B[i], A[i]


def count_ones(num):
    num = (num & 0x55555555) + (num >> 1 & 0x55555555)
    num = (num & 0x33333333) + (num >> 2 & 0x33333333)
    num = (num & 0x0F0F0F0F) + (num >> 4 & 0x0F0F0F0F)
    num = (num & 0x00FF00FF) + (num >> 8 & 0x00FF00FF)
    num = (num & 0x0000FFFF) + (num >> 16 & 0x0000FFFF)
    return num


ans = 0

for bi in range(1 << N):
    # bi<<i : iはBが表で終わるか
    if count_ones(bi) % 2 == 1:
        continue
    L = [((B[i], True, i) if bi << i else (A[i], False, i)) for i in range(N)]

    R = sorted(L)
    ans = 0
    for i in range(N-1):
        Lval, Lbool, Li = L[i]
        Rval, Rbool, Ri = R[i]
        if Li != Ri:
            ans += 1
            L[Li], L[Ri] = L[Ri], L[Li]
    if L == R:
        print(ans)
        import sys
        sys.exit()

print(-1)

Submission status: Wrong Answer

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

INF = 10000

tentou = 0
def merge_sort(array, L, R):
    global tentou
    if R - L <= 1:
        return array[L:R]
    MID = L + (R-L)//2
    left = merge_sort(array, L, MID)
    right = merge_sort(array, MID, R)
    LL = MID - L
    RL = R - MID
    array = []
    il = 0
    ir = 0
    while il < LL and ir < RL:
        if left[il] <= right[ir]:
            array.append(left[il])
            il += 1
        else:
            tentou += 1
            array.append(right[ir])
            ir += 1
    if il < LL:
        array.extend(left[il:])
    if ir < RL:
        array.extend(right[ir:])
    return array

def merge_sort2(array, L, R):
    global tentou
    if R - L == 1:
        return array[L:L+1]
    MID = L + (R-L)//2
    left = merge_sort(array, L, MID)
    right = merge_sort(array, MID, R)
    LL = MID - L
    RL = R - MID
    array = []
    il = 0
    ir = 0
    while il < LL and ir < RL:
        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 < RL:
        array.extend(right[ir:])
    return array

ans = INF
is_odd = (N % 2) == 1
for bits in product(range(2), repeat=N):
    odds = []
    evens = []
    for i, bit in enumerate(bits):
        if (i % 2 == 0 and bit) or (i % 2 == 1 and not bit):
            odds.append((As[bit][i], i))
        else:
            evens.append((As[bit][i], i))
    Lodds = len(odds)
    Levens = len(evens)
    if (is_odd and Lodds != Levens+1) or ((not is_odd) and Lodds != Levens):
        continue
    odds = merge_sort2(odds, 0, Lodds)
    evens = merge_sort2(evens, 0, Levens)
    prev = 0
    arr = []
    for o, e in zip_longest(odds, evens):
        if o[0] < prev:
            break
        if e and e[0] < o[0]:
            break
        arr.append(o[1])
        if e:
            arr.append(e[1])
            prev = e[0]
    else:
        tentou = 0
        arr = merge_sort(arr, 0, N)
        ans = ans if ans < tentou else tentou

if ans == INF:
    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()))

X = [(A[i], i) for i in range(N)]
Y = [(B[i], i) for i in range(N)]


def change(i, j):
    A[i], B[i], A[j], B[j] = B[j], A[j], B[i], A[i]


def count_ones(num):
    num = (num & 0x55555555) + (num >> 1 & 0x55555555)
    num = (num & 0x33333333) + (num >> 2 & 0x33333333)
    num = (num & 0x0F0F0F0F) + (num >> 4 & 0x0F0F0F0F)
    num = (num & 0x00FF00FF) + (num >> 8 & 0x00FF00FF)
    num = (num & 0x0000FFFF) + (num >> 16 & 0x0000FFFF)
    return num


ans = 0

for bi in range(1 << N):
    # bi<<i : iはBが表で終わるか
    if count_ones(bi) % 2 == 1:
        continue
    L = [((B[i], True, i) if bi << i else (A[i], False, i)) for i in range(N)]

    R = sorted(L)
    ans = 0
    for i in range(N-1):
        Lval, Lbool, Li = L[i]
        Rval, Rbool, Ri = R[i]
        if Li != Ri:
            ans += 1
            L[Li], L[Ri] = L[Ri], L[Li]
    if L == R:
        print(ans)

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import math

def first(i,a,b):
    if i%2==0: return [a,b]
    else: return [b,a]

def chk(a,b):
    if n%2==0:
        for i in range(m-1):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0
        if a[m-1][0]>b[m-1][0]: return 0
            
    else:
        for i in range(m-1):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0

    return 1

def cal(a,b):
    l=[]
    if n%2==0:
        for i in range(m):
            l+=[a[i][1],b[i][1]]
    if n%2==1:
        for i in range(m-1):
            l+=[a[i][1],b[i][1]]
        l.append(a[m-1][1])
    return l
        


n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if n==1:
    print(0)
    sys.exit()

x=[first(i,a[i],b[i]) for i in range(n)]
x.sort()

m=math.ceil(n/2)
p=[i for i in range(n)]
ans=1000000

for q in list(itertools.combinations(p,m)):
    tmpa,tmpb=[],[]
    for i in range(n):
        if i in q: tmpa.append( [a[i],i] )
        else: tmpb.append([b[i],i])
    tmpb.sort()

    if chk(tmpa,tmpb)==1:
        s=[0 for i in range(n)]
        t=cal(tmpa,tmpb)
        tans=0
        for i in range(n-1):
            for j in range(1,n):
                if a[i]>a[j]: tans+=1
        ans=min(ans,tans)

print(ans//2 if ans<1000000 and ans%2==0 else -1)

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import combinations
    from operator import itemgetter

    n = int(input())
    if n == 1:
        print(0)
        return

    *a, = map(int, input().split())
    *b, = map(int, input().split())

    if n == 2:
        if a[0] <= a[1]:
            print(0)
            return
        elif b[1] <= b[0]:
            print(1)
            return
        else:
            print(-1)
            return

    evens = []
    for i in range(n):
        if i % 2 == 0:
            evens.append(a[i])
        else:
            evens.append(b[i])

    odds = []
    for i in range(n):
        if i % 2 == 0:
            odds.append(b[i])
        else:
            odds.append(a[i])

    def is_ok(e, o):
        n = len(e) + len(o)
        p = 0
        for i in range(n):
            if i % 2 == 0:
                if p > e[i // 2]:
                    return False
                p = e[i // 2]
            else:
                if p > o[i // 2]:
                    return False
                p = o[i // 2]
        return True

    ret = 100
    st = set(range(n))
    for AbCdE in combinations(range(n), n - n // 2):
        e = itemgetter(*AbCdE)(evens)
        aBcDe = st.difference(AbCdE)
        o = itemgetter(*aBcDe)(odds)
        if n == 3:
            o = (o,)

        *se, = sorted(e)
        *so, = sorted(o)

        if is_ok(se, so):
            curr_se = 0
            for j, se_ in enumerate(se):
                k = evens.index(se_)
                curr_se += abs(k - j * 2)
            curr_so = 0
            for j, so_ in enumerate(so):
                k = odds.index(so_)
                curr_so += abs(k - j * 2 - 1)
            ret = min(ret, max(curr_se, curr_so))

    if ret < 100:
        print(ret)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    INF = float('inf')

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    ans = INF
    for S in range(2**N):
        nums = [0, 0]
        for i in range(N):
            if S & (1<<(N-1-i)):
                nums[i%2] += 1
        if nums[0] != nums[1]: continue

        Cs = []
        for i, (A, B) in enumerate(zip(As, Bs)):
            if S & (1<<(N-1-i)):
                Cs.append(B)
            else:
                Cs.append(A)

        num = 0
        useds = [False] * N
        Ds = [0] * N
        for p in range(N):
            minC = INF
            iMinC = -1
            for i in range(N):
                m = 1<<(N-1-i)
                if useds[i]: continue
                if p%2 == 0:
                    if (i%2 == 0 and S&m == 0) or (i%2 and S&m):
                        if Cs[i] < minC:
                            minC = Cs[i]
                            iMinC = i
                else:
                    if (i%2 == 0 and S&m) or (i%2 and S&m == 0):
                        if Cs[i] < minC:
                            minC = Cs[i]
                            iMinC = i
            if iMinC == -1:
                break
            num += abs(p-iMinC)
            useds[iMinC] = True
            Ds[p] = Cs[iMinC]
        else:
            for i in range(N-1):
                if Ds[i+1] < Ds[i]:
                    break
            else:
                num //= 2
                ans = min(ans, num)

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


solve()

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)
    m=min(m,(v+w)*3)
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()))

X = [(A[i], i) for i in range(N)]
Y = [(B[i], i) for i in range(N)]


def change(i, j):
    A[i], B[i], A[j], B[j] = B[j], A[j], B[i], A[i]


def count_ones(num):
    num = (num & 0x55555555) + (num >> 1 & 0x55555555)
    num = (num & 0x33333333) + (num >> 2 & 0x33333333)
    num = (num & 0x0F0F0F0F) + (num >> 4 & 0x0F0F0F0F)
    num = (num & 0x00FF00FF) + (num >> 8 & 0x00FF00FF)
    num = (num & 0x0000FFFF) + (num >> 16 & 0x0000FFFF)
    return num


ans = 0

for bi in range(1 << N):
    # bi<<i : iはBが表で終わるか
    if count_ones(bi) % 2 == 1:
        continue
    L = [((B[i], True, i) if bi << i else (A[i], False, i)) for i in range(N)]

    R = sorted(L)
    ans = 0
    for i in range(N):
        Lval, Lbool, Li = L[i]
        Rval, Rbool, Ri = R[i]
        if Li != Ri:
            ans += 1
            L[Li], L[Ri] = L[Ri], L[Li]
    if L == R:
        print(ans)

print(-1)

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],j] if s[j] == "0" else [blue[j],j+1,j] for j in range(n)]
    num.sort()
    key = 1
    nu = 0
    for h in range(n):
        nu += abs(num[h][-1]-h)
        if (num[h][1]-h) % 2 != 0:
            key = 0
    if key:
        ans = min(ans,nu//2)
if ans == 10 ** 5:
    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 = 10**9
for i in range(2**N):
    cand = 0
    i = bin(i)[2:]
    i = '0'*(N-len(i))+i
    l0 = []
    for j in range(N):
        if i[j]=='0':
            l0.append([A[j],j])
        else:
            l0.append([B[j],j])
    l1 = sorted(l0)
    for j in range(N):
        k = l1[j][0]
        for l in range(len(l0)+1):
            if l == len(l0):
                break
            if l0[l][0]==k:
                if (l0[l][1]-l)%2==0 and i[l0[l][1]]=='0':
                    cand += l
                    break
                if (l0[l][1]-l)%2==1 and i[l0[l][1]]=='1':
                    cand += l
                    break
        if l==len(l0):
            cand = 10**9
            break
        l0 = l0[:l]+l0[l+1:]
    ans = min(ans,cand)

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

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = -1

# def chk(a):
#     for i in range(N-1):
#         if a[i] > a[i+1]:
#             return False
#     return True

def cnt(idx):
    res = 0
    for i in range(N):
        res += abs(idx[i] - i)
    return res // 2

for idx in permutations(range(N)):
    # print(idx)
    a = []
    flg = True
    for i in range(N):
        if (idx[i] % 2) ^ (i%2):
            a.append(B[idx[i]])
        else:
            a.append(A[idx[i]])
        if i and (a[i-1] > a[i]):
            flg = False
            break
    # print(a)
    if flg:
        if ans == -1:
            ans = cnt(idx)
        else:
            ans = min(ans, cnt(idx))

print(ans)