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:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = len(set(A))
D = len(set(B))
for i in range(N):
    A[i] = [A[i],i+1]
    B[i] = [B[i],i+1]
A = sorted(A)
B = sorted(B)
idx = 0
A_d = 0
while True:
    if idx >= len(A):
        break
    if A[idx][1] == idx + 1:
        pass
    else:
        A_d += abs(A[idx][1]-(idx-1))
        A = A[idx+1:]
        for i in range(N-(idx+1)):
            A[i] = [A[i],i+1]
    idx += 1
idx = 0
B_d = 0
while True:
    if idx >= len(B):
        break
    if B[idx][1] == idx + 1:
        pass
    else:
        B_d += abs(B[idx][1]-(idx-1))
        B = B[idx+1:]
        for i in range(N-(idx+1)):
            B[i] = [B[i],i+1]
    idx += 1

if A_d % 2 == 0:
    pass
else:
    if N == C:
        A_d = -1
    else:
        A_d += 1
if B_d % 2 == 0:
    if N == D:
        B_d = -1
    else:
        B_d += 1
else:
    pass
if A_d == B_d == -1:
    print(-1)
else:
    if A_d == -1:
        A_d = B_d+1
    if B_d == -1:
        B_d = A_d+1
    print(min(A_d,B_d))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
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=deque()
    stack.append((0,0,[],[True]*N))
    kouho=[]
    while stack:
        n,index,l,f=stack.popleft()
        if index==N:
            kouho.append(l)
            if len(kouho)>100:
                break
            continue
        
        if index%2:
            C=l_even
        else:
            C=l_odd
        for a in C[:N-(N-index)//2+1]:
            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 itertools import permutations as p
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
an=float("INF")
for i in range(0,n,2):
    for j in p([0]*(n-i)+[1]*i,n):
        c=[]
        for h in range(n):
            if j[h]:
                c.append([b[i],1])
            else:
                c.append([a[i],0])
        d=sorted(c)
        x,y,z=0,0,0
        f=0
        for s in range(n):
            if c[i]==d[i]:
                if d[i][1]==1:
                    x+=1
            else:
                if d[i][1]==1:
                    y+=1
                else:
                    z+=1
        if (x+y)%2==1:
            break
        else:
            an=min(an,(x+y+z)//2)
print(-1 if an==float("INF") else an)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_lis = list(map(int, input().split()))
b_lis = list(map(int, input().split()))
used = []
res = -1

queue = [(a_lis, b_lis, 0, 0)]

while queue:
    cur_a_lis, cur_b_lis, l, pre_i = queue.pop(0)
    
    found = True
    pre = -1
    for a in cur_a_lis:
        if a < pre:
            found = False
            break
        pre = a
    if found:
        res = l
        break
    used.append((cur_a_lis, cur_b_lis))
    for i in range(pre_i, len(cur_a_lis) - 1):
        na_lis = cur_a_lis[:i] + [cur_b_lis[i + 1]] + [cur_b_lis[i]] + cur_a_lis[i + 2:]
        nb_lis = cur_b_lis[:i] + [cur_a_lis[i + 1]] + [cur_a_lis[i]] + cur_b_lis[i + 2:]
        if (na_lis, nb_lis) not in used:
            queue.append((na_lis, nb_lis, l + 1, i))
print(res)

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)
            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 sortable(m, A, B):
    if len(A) == 2:
        if m <= A[0] <= A[1]:
            return 0
        elif m <= B[1] <= B[0]:
            return 1
        return -1
    t = 10**9
    for i in range(len(A)):
        n = A[i] if i % 2 == 0 else B[i]
        if n < m:
            continue
        x = sortable(n, B[0:i] + A[i + 1:], A[0:i] + B[i + 1:])
        if x >= 0:
            t = min(t, x + i)
    if t != 10 ** 9:
        return t
    return -1


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    if len(A) == 1:
        print(1)
    else:
        print(sortable(0, A, B))

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa


def solve(N: int, A: "List[int]", B: "List[int]"):

    cand = []
    # n-bitが立っていれば, n枚目は裏を見る
    for i in range(2**N):
        if bit_sum(i) % 2 == 1:
            continue

        even, odd = 0, 0
        j = i
        c = 0
        while j > 0:
            if c % 2 == 0:
                even += j & 1
            else:
                odd += j & 1
            j >>= 1
            c += 1
        if even != odd:
            continue

        card = [(B[j], A[j], j, (i >> j) & 1) if (i >> j) & 1 else (A[j], B[j], j, (i >> j) & 1)
                for j in range(N)]
        card.sort()

        flag = True
        count = 0
        for j in range(N):
            omote, ura, nth, ove = card[j]
            if ove == 1 and (j % 2 == nth % 2):
                flag = False
                break
            elif ove == 0 and (j % 2 != nth % 2):
                flag = False
                break
            else:
                count += abs(nth-j)
        if flag:
            # print(*card, sep="\n")
            cand.append((i, count//2))

        # print(card)
    if len(cand) == 0:
        print(-1)
    else:
        print(min([c for _, c in cand]))


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:
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() #実現したい数列
        
        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}
                    move += (o - j if o >= j else 0)
 
                    break
                elif abs(j - o) % 2 == 1 and B[o] == n:
                    original[n] -= {o}
                    move += (o - j if o >= j else 0)
                    
                    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:
import itertools
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

od=[A[i] if i%2==0 else B[i] for i in range(N)]
ev=[B[i] if i%2==0 else A[i] for i in range(N)]

ans=float("inf")
for v in itertools.combinations(range(1,N+1),N//2):
  v=[i for i in v]
  o=[]
  e=[]
  for i in range(1,N+1):
    if i in v:
      if i%2==0:
        e.append([A[i-1],i])
      else:
        e.append([B[i-1],i])
    else:
      if i%2==0:
        o.append([A[i-1],i])
      else:
        o.append([B[i-1],i])
  e.sort()
  o.sort()
  v=[e[i//2][1] if i%2==1 else o[i//2][1] for i in range(N)]
  n=0
  j=1

  if j==1:
    a=0
    r=list(range(1,N+1))
    while v:
      a+=r.index(v[0])
      r.remove(v[0])
      v.pop(0)
    ans=min(ans,a)
    
if ans==float("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()))
ans = float("inf")
  
for i in range(2**n):
  L = []
  G = []
  for j in range(n):
    if i>>j & 1:
      L.append(B[j])
      G.append(1)
    else:
      L.append(A[j])
      G.append(0)
  C = [0]*n
  cnt = 0
  D = [set() for _ in range(51)]
  for a in range(n-1):
    for b in range(a+1, n):
      if L[a] > L[b]:
        C[a] ^= 1
        C[b] ^= 1
        cnt += 1
      elif L[a] == L[b]:
        D[L[a]].add(a)
        D[L[a]].add(b)
  K = [i for i in D if i]
  for i in K:
    l = sorted(list(i))
    m = len(l)
    if C[l[-1]] ^ G[l[-1]]:
      break
    for j in range(m-1):
      if C[l[j]] ^ G[l[j]]:
        C[l[j]] ^= 1
        if G[l[j]]:
          cnt += 1
  if C == G:
    ans = min(ans, cnt)
if ans == float("inf"):
  print(-1)
else:
  print(ans)

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()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**n:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
nn=2**n
ans=float("inf")
for i in range(nn):
  C=[]
  for j in range(n):
    if i&(1<<j)==0:
      C.append(A[j]*10000+j*100+0)
    else:
      C.append(B[j]*10000+j*100+1)

  C.sort()

  chk=True
  for ii in range(n):
    c1,c2=(C[ii]%10000)//100,C[ii]%100
    if (c1-c2-ii)%2==0:
      continue
    else:
      chk=False
      break
  if chk:
    ct=0
    BIT=[0]*nn
    BIT.insert(0,0)
    for i1 in range(n):
      c=(C[i1]%10000)//100+1
      ct+=i1-bitsum(BIT,c)
      bitadd(BIT,c,1)


    
    ans=min(ans,ct)
print(-1 if ans==float("inf") else ans)

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)
            if len(kouho)>1000:
                break
            continue
        
        if index%2:
            C=l_even
        else:
            C=l_odd
        for a in C[:N-(N-index)//2+1]:
            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:
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
        dd = d.copy()
        dd[0][index], dd[1][index] = 100, 100

        ret = select(dd, index_list + [index], d[uo][index])

        if ret != -1:
            break
        else:
            d[uo][index] = 100
    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 sys
sys.setrecursionlimit(10 ** 9)
from bisect import bisect_left

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [(x, i) for i, x in enumerate(lr())]
B = [(x, i) for i, x in enumerate(lr())]
odd = A[::2] + B[1::2] #奇数番目のカードでしか表にならない
even = A[1::2] + B[::2]
odd.sort()
even.sort()
# 最初のカードを全通り試す

def F(i, right, OE, OE2, x, used, count):
    global answer
    #左からi番目にOE(oddかeven)のsortした後のx番目のカードを入れる
    #今まで使ったカードはused、操作回数はcount(最後に２で割る)
    used.add(OE[x][1])
    count += abs(i-OE[x][1])
    right = OE[x][0]
    if i == N-1:
        count //= 2
        if count < answer:
            answer = count
        return
   
    j = bisect_left([y for y, z in OE2], right)   
    for k in range(j, N):
        if OE2[k][1] in used:
            continue
        F(i+1, right, OE2, OE, k, used, count)

INF = 10 ** 19
answer = INF
for i in range(N):
    F(0, 0, odd, even, i, set(), odd[i][1])

print(answer if answer < INF else -1)

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()))
res = float("inf")
for i in range(pow(2, N)):
  x = []
  l = []
  c = 0
  for j in range(N):
    if i & (1 << j):
      c += 1
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  if c % 2: continue
  y = sorted(x, key = lambda x: x[0])
  z = -1
  #print(y, i)
  for j in range(N):
    t = abs(j - y[j][1])
    #print(i & (1 << y[j][1]) > 0, t)
    if i & (1 << j) > 0:
      if t % 2:
        z = max(z, t)
      else:
        z = -1
        break
    else:
      if t % 2 == 0:
        z = max(z, t)
      else:
        z = -1
        break
  if z == -1: continue
  z = 0
  for j in range(N):
    for k in range(j, N):
      if x[k][0] == y[j][0]:
        x.pop(k)
        x.insert(0, (0, 0))
        z += k - j
        break
  res = min(res, z)

  
if res != float("inf"): print(res)
else: 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()]
AB = sorted(list(set(A + B)))
D = {ab: i+1 for i, ab in enumerate(AB)}
A = [D[a] for a in A]
B = [D[a] for a in B]

def chk(L):
    NN = 5
    BIT=[0] * (2**NN+1)
    def addbit(i):
        while i <= 2**NN:
            BIT[i] += 1
            i += i & (-i)

    def getsum(i):
        ret = 0
        while i != 0:
            ret += BIT[i]
            i -= i&(-i)
        return ret
    s = 0
    for l in L[::-1]:
        s += getsum(l+1)
        addbit(l+1)
    return s
ans = 1 << 100
for m in range(1<<N):
    if bin(m).count("1") & 1: continue
    C = [[], []]
    for i in range(N):
        p = m >> i & 1
        q = p + i & 1
        C[q].append(A[i] if p == 0 else B[i])
    CC = sorted(C[0] + C[1])
    if CC[::2] != sorted(C[0]): continue
    CCC = [C[i%2][i//2] for i in range(N)]
    ans = min(ans, chk(CCC))
print(ans 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()))
ans = 10**9+7
for i in range(2**N):
    card = [[],[]]
    num = []
    for j in range(N):
        if i&1:
            num.append(B[j])
            card[(j+1)%2].append(j)
        else:
            num.append(A[j])
            card[(j)%2].append(j)
        i >>= 1
    if len(card[1]) != N//2:
        continue
    card[0].sort(key=lambda x:[num[x],x])
    card[1].sort(key=lambda x:[num[x],x])
    hoge = []
    for i in range(N):
        hoge.append(card[i%2][i//2])
    flag = True
    for i in range(N-1):
        if num[hoge[i]] > num[hoge[i+1]]:
            flag = False
    if flag:
        huga = sum(abs(hoge[i]-i)for i in range(N))//2
        if huga < ans:
            ans = huga
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)


def dp(i, swap=False, memo={}):
    if i >= N:
        return 0
    if (i, swap) in memo:
        return memo[i, swap]
    res = float('inf')
    if A[i - 1] <= A[i]:
        res = min(res, dp(i + 1, False))
    if B[i] <= B[i - 1]:
        A[i], A[i - 1] = A[i - 1], A[i]
        B[i], B[i - 1] = B[i - 1], B[i]
        A[i], A[i - 1], B[i], B[i - 1] = B[i], B[i - 1], A[i], A[i - 1]
        res = min(res, 1 + dp(i + 1, True))
        A[i], A[i - 1] = A[i - 1], A[i]
        B[i], B[i - 1] = B[i - 1], B[i]
        A[i], A[i - 1], B[i], B[i - 1] = B[i], B[i - 1], A[i], A[i - 1]
    memo[i, swap] = res
    return res


N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
memo = {}
res = dp(1, False, memo)
A[0], B[0] = B[0], A[0]
res = min(1 + dp(1, True, memo), res)
if res != float('inf'):
    print(res)
else:
    print(-1)

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)
            if len(kouho)>100:
                break
            continue
        
        if index%2:
            C=l_even
        else:
            C=l_odd
        for a in C[:N-(N-index)//2+1]:
            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:
print(1)

Submission status: Wrong Answer

Solution code:
def main():
    from random import shuffle
    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)

        for j in range(5):
            res = A[:]
            now = B[:]
            ans = 0
            flag = True
            k = list(range(N - 1))
            shuffle(k)
            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:
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


def make_card():
    card = []
    for i in range(n):
        a, b = A[i], B[i]
        if i % 2 == 0:
            card.append([a, b, i])
        else:
            card.append([b, a, i])
    card.sort()
    return card


def even(arr):
    arr.sort()
    for i in range(len(arr)):
        if ans[-1][1] <= arr[i][0]:
            a = arr.pop(i)
            ans.append(a)
            return False
    return True


def odd(arr):
    arr.sort(key=lambda x: x[1])
    for i in range(len(arr)):
        if ans[-1][0] <= arr[i][1]:
            a = arr.pop(i)
            ans.append(a)
            return False
    return True


C = []
for i in range(n):
    card = make_card()
    c = card.pop(i)
    ans = [c]
    for j in range(1, n):
        if j % 2 == 0:
            f = even(card)
        else:
            f = odd(card)
        if f:
            break
    else:
        cnt = 0
        for i in range(n):
            cnt += abs(ans[i][2] - i)
        cnt //= 2
        C.append(cnt)

if C == []:
    print(-1)
else:
    print(min(C))

Submission status: Wrong Answer

Solution code:
from itertools import product


def solve(n, a_list, b_list):
    res = 10 ** 9 + 7
    v_dict_from = dict()
    v_dict_to = dict()

    for p in product([0, 1], repeat=n):
        if sum(p) % 2 == 1:
            continue
        q = [0] * n
        position_now = list(range(n))
        r = 0

        c_list = [a for a in a_list]
        for i in range(n):
            if p[i] == 1:
                c_list[i] = b_list[i]
        c_list_s = list(sorted(c_list))
        for v in range(1, 51):
            v_dict_from[v] = []
            v_dict_to[v] = []
        for i in range(n):
            v_dict_from[c_list[i]].append(i)
            v_dict_to[c_list_s[i]].append(i)
        # print(v_dict_from)
        # print(v_dict_to)
        for v in range(1, 51):
            for j, k in zip(list(sorted(v_dict_from[v])), v_dict_to[v]):
                for i in range(n):
                    if k <= position_now[i] < position_now[j]:
                        q[i] += 1
                        q[j] += 1
                        position_now[i] += 1
                        r += 1
                position_now[j] = k

            d = 0
            for j in v_dict_from[v]:
                if q[j] % 2 != p[j]:
                    d += 1
            if d % 2 == 0:
                r += d // 2
            else:
                r += 10 ** 9 + 7

        res = min(res, r)
    if res < 10 ** 9 + 7:
        return res
    else:
        return -1


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    res = solve(n, a_list, b_list)
    print(res)


def test():
    assert solve(3, [3, 4, 3], [3, 2, 3]) == 1
    assert solve(2, [2, 1], [1, 2]) == -1
    assert solve(4, [1, 2, 3, 4], [5, 6, 7, 8]) == 0


if __name__ == "__main__":
    test()
    main()

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+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:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()
B = inpl()

def bubble_sort(input_list, key):
    total_number = len(input_list)
    flag = True
    finished = 0
    tmp = 0

    while flag:
        flag = False
        for i in range(total_number-1-finished):
            if key[input_list[i]] > key[input_list[i+1]]:
                input_list[i], input_list[i+1] = input_list[i+1], input_list[i]
                tmp += 1
                flag = True
        finished += 1
    return input_list, tmp

ans = 10**9
g0 = itemgetter(0)
X = [0]*N
C = [0]*N
for i in range(2**N):
    I = i*1

    blue = 0
    for j in range(N):
        if I%2:
            X[j] = A[j]
            C[j] = 0
        else:
            X[j] = B[j]
            C[j] = 1
            blue += 1
        I //= 2
    if blue%2 == 1:
        continue
    I = list(range(N))
    I, tmp = bubble_sort(I, key=X)
    l = 0
    r = 0
    while l < N:
        for r in range(l, N):
            if X[I[l]] != X[I[r]]:
                break
        else:
            r = N
        p = 0
        for x in range(l, r-1):
            if (abs(x - I[x])+p)%2 != C[I[x]]:
                tmp += 1
                p = 1
            else:
                p = 0
        x = r-1
        if (abs(x - I[x]) + p)%2 != C[I[x]]:
            tmp = -1
            break
        l = r
    if (tmp != -1):
        ans = min(tmp, ans)
if (ans == 10**9):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
print(18)