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()))
odd = []
even = []

for i in range(n):
    if i % 2 == 0:
        even.append(a[i])
        odd.append(b[i])
    else:
        even.append(b[i])
        odd.append(a[i])
#odd, evenの二部グラフで、自身に辺を通さない
#a[i] <=  b[j]の時辺を通す 
graph = [[0 for __ in range(n*2)] for _ in range(n*2)]
for i in range(n):
    for j in range(n, n*2):
        if i != j % n and even[i] <= odd[j%n]:
            graph[i][j] = 1

for i in range(n,n*2):
    for j in range(n):
        if  j != i % n and odd[i % n] <= even[j]:
            graph[i][j] = 1
#グラフで一筆書きをする。パスがnになったら終わり。その順番を実現するために考える
def clear_maze(start, finished, path):
    finished.add(start % n)
    path = path + [start]
    if len(path) == n:
        check(path)
    else:
        for i in range(n*2):
            # この辺でバグってる
            if (i % n not in finished) and graph[start][i] == 1:
                clear_maze(i, finished, path)
def check(path):
    #この順番に並ぶための最小
    #print(path)
    array = [i % n for i in path]
    cand = 0
    global ans
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if array[j] < array[j-1]:
                tmp = array[j]
                array[j] = array[j-1]
                array[j-1] = tmp
                cand += 1
    ans = min(cand, ans)
inf = 10**10
ans = inf
#for i in range(n*2):
#    print(graph[i])
for i in range(n*2):
    #iから始める迷路を解く
    clear_maze(i, set(), [])
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()))
odd = []
even = []

for i in range(n):
    if i % 2 == 0:
        even.append(a[i])
        odd.append(b[i])
    else:
        even.append(b[i])
        odd.append(a[i])
#odd, evenの二部グラフで、自身に辺を通さない
#a[i] <=  b[j]の時辺を通す 
graph = [[0 for __ in range(n*2)] for _ in range(n*2)]
for i in range(n):
    for j in range(n, n*2):
        if i != j % n and even[i] <= odd[j%n]:
            graph[i][j] = 1

for i in range(n,n*2):
    for j in range(n):
        if  j != i % n and odd[i % n] <= even[j]:
            graph[i][j] = 1
#グラフで一筆書きをする。パスがnになったら終わり。その順番を実現するために考える
def clear_maze(start, finished, path):
    finished.add(start % n)
    path = path + [start]
    if len(path) == n:
        check(path)
    else:
        for i in range(n*2):
            # この辺でバグってる
            if (i % n not in finished) and graph[start][i] == 1:
                clear_maze(i, finished, path)
def check(path):
    #この順番に並ぶための最小
    print(path)
    array = [i % n for i in path]
    cand = 0
    global ans
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if array[j] < array[j-1]:
                tmp = array[j]
                array[j] = array[j-1]
                array[j-1] = tmp
                cand += 1
    ans = min(cand, ans)
inf = 10**10
ans = inf
for i in range(n*2):
    print(graph[i])
for i in range(n):
    #iから始める迷路を解く
    clear_maze(i, set(), [])
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()))

#0-indexed

#カードiが左からjの位置にあるときの表の数字
def getNum(i,j):
    return B[i] if abs(i-j)&1 else A[i]

#dp[使用済みカードを表すbit列][いちばん右のカードNo]=最小操作回数
INF=10**9
dp=[[INF for _ in range(N)] for __ in range(1<<N)]
for i in range(N):
    dp[1<<i][i] = i

for m in range(1,1<<N): #配置済みカードパターン
    cnt=bin(m).count('1') #配置済みカード数
    for j in range(N): #新たに並べるカード
        if m & (1<<j):
            #もう使ったやつです
            continue
        num_j=getNum(j,cnt)
        for i in range(N): #配置済みのいちばん右にあるカード
            if m & (1<<i) == 0:
                #まだ配置済みじゃないです
                continue
            num_i=getNum(i,cnt-1)
            if num_i>num_j:
                #単調増加になりません
                continue
            dp[m|(1<<j)][j] = min(dp[m|(1<<j)][j], dp[m][i] + max(0,j-cnt))

ans=INF
for i in range(N):
    ans=min(ans,dp[(1<<N)-1][i])
print(ans if ans<INF else -1)

Submission status: Wrong Answer

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

#a = list(map(int, input().split()))

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

dp = [[[999999,[],0] for _ in range(n)] for _ in range(2**n)]
queset = [[0 for _ in range(n)] for _ in range(2**n)]

dp[0][0][0]=0
que = [[0,0]] #[bit, num of right]
done = 0
sq2 = [2**i for i in range(20)]
good = [999 for i in range(n+1)]

while(len(que) > done):
    now = que[done]
    done +=1
    nowBits = ValueToBits(now[0],n)
    sumBits = sum(nowBits) # 既に何枚使ったか
    nowTentou = dp[now[0]][now[1]][0]
    nowCards = []
    Tentous = [0 for i in range(n)]
    for i in range(n):
        if(nowBits[i]==1):
            nowCards.append(i)
            Tentous[i] = Tentous[i-1]+1 if i>=1 else 1
        else:
            Tentous[i] = Tentous[i-1] if i>=1 else 0
    nowRight = dp[now[0]][now[1]][2]
    #if(len(nowCards)>0): print(len(nowCards),nowCards[-1],nowRight)
    for i in range(n):
        if(nowBits[i] == 0 and nowTentou<good[sumBits]+10):
            # 右端に今加えようとしてるカード i は表か裏か
            UpDown = abs(i-sumBits)%2
            # 右端を加えた集合
            nextValue = now[0] + sq2[i]

            #nextCards = list(nowCards)
            #nextCards.append(i)
            nextRight = A[i] if UpDown==0 else B[i]
            #print(nextCards)
            if(nowRight <= nextRight):
                #print(nowRight,nextRight)
                nextTentou = nowTentou + (sumBits - Tentous[i])
                #for k in nowCards:
                #    if(k > i):
                #        nextTentou+=1
                #print(dp[nextValue][i][0] , nextTentou)
                if(dp[nextValue][i][0] > nextTentou):
                    dp[nextValue][i][0] = nextTentou
                    if(good[sumBits+1] > nextTentou): good[sumBits+1]=nextTentou
                    #dp[nextValue][i][1] = list(nextCards)
                    dp[nextValue][i][2] = nextRight
                    if(queset[nextValue][i]==0):
                        que.append([nextValue, i])
                        queset[nextValue][i]=1
                    #print(dp[nextValue][i])
#print()
ans=999999
for i in range(n):
    if(ans > dp[2**n-1][i][0]):
        ans = dp[2**n-1][i][0]
if(ans>99998):
    print(-1)
else:
    print(ans)
#print(len(que))
#print(good)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict
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

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += i-bit.sum(p)
        bit.add(p, 1)
    return ans
N = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
us = []
vs = []
for i in range(N):
    a, b = xs[i], ys[i]
    if i%2:
        us.append((a,i))
        vs.append((b,i))
    else:
        us.append((b,i))
        vs.append((a,i))
us.sort()
vs.sort()
r = 10**18
for i in range(2**N):
    t = 0
    tt = 0
    rs = [0]*N
    for j in range(N):
        if i%2:
            if 2*t < N:
                rs[t*2] = us[j]
            t += 1
        else:
            if 2*tt+1 < N:
                rs[tt*2+1] = us[j]
            tt += 1
        i = i>>1
    if t != (N+1)//2:
        continue
    b,ff = 0,0
    for z,j in rs:
        if b>z:
            ff = 1
            break
        b = z
    if ff:
        continue
    rs = [j+1 for _,j in rs]
    r = min(r, tento(rs))
print(r if r != 10**18 else -1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
judge = False
ans = 10**9
for i in range(2**N):
  l = []
  x = 0
  for j in range(N):
    if ((i>>j) & 1):
      l.append([B[j],j,1])
      
    else:
      l.append([A[j],j,0])
  for m in range(N):
    for n in range(N-1,m,-1):
      if l[n][0]<l[n-1][0]:
        l[n],l[n-1]=l[n-1],l[n]
        x+=1

  tmp = True
  for o in range(N):
    if abs(l[o][1]-o)%2==l[o][2]:
      continue
    else:
      if o==N-1:
        tmp = False
        break
      b=False
      y=1
      while True:
        if o+y>N-1:
          break
        if l[o][0]==l[o+y][0]:
          if abs(l[o+y][1]-o-1)%2!=l[o+y][2]:
            l[o],l[o+y]=l[o+y],l[o]
            x+=2*y-1
            b=True
            break
          else:
            y+=2   
        else:
          break
      if b:
        continue
      tmp = False
      break
  if tmp:
    judge=True
    ans = min(ans,x)
    
if judge:
  print(ans)
  
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,v=[],[],[]
    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],
            v+=b[j],
        else:
            if j%2:
                u+=a[j],
            else:
                t+=a[j],
            v+=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)
    w=0
    for j,p in enumerate(v):
        bit.add(p,1)
        w+=j+1-bit.sum(p)
    m=min(m,w)
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()))
judge = False
ans = 10**9
for i in range(2**N):
  l = []
  x = 0
  for j in range(N):
    if ((i>>j) & 1):
      l.append([B[j],j,1])
      
    else:
      l.append([A[j],j,0])
  for m in range(N):
    for n in range(N-1,m,-1):
      if l[n][0]<l[n-1][0]:
        l[n],l[n-1]=l[n-1],l[n]
        x+=1

  tmp = True
  for o in range(N):
    if abs(l[o][1]-o)%2==l[o][2]:
      continue
    else:
      if o==N-1:
        tmp = False
        break
      if l[o][0]==l[o+1][0]:
        if abs(l[o+1][1]-o-1)%2!=l[o+1][2]:
          l[o],l[o+1]=l[o+1],l[o]
          x+=1
          continue
      tmp = False
      break
  if tmp:
    judge=True
    ans = min(ans,x)
    
if judge:
  print(ans)
  
else:
  print(-1)

Submission status: Wrong Answer

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

def solve(N: int, A: "List[int]", B: "List[int]"):
    answer = 10**18
 
    ## 奇数indexにくるものを決め打ち
    for c in combinations(range(N), N//2):
        even, odd= [], []
        
        for i in range(N):
            if i in c:
                odd.append((A[i] if i % 2 == 1 else B[i],i))
            else:
                even.append((A[i] if i % 2 == 0 else B[i],i))
    
        even.sort()
        odd.sort()
        t = []
        
        for i in range(N//2):
            t.append(even[i])
            t.append(odd[i])

        if N%2 == 1:
            t.append(even[-1])
        
        if t != sorted(t):
            continue

        tentousuu = 0
        for i in range(N-1):
            for j in range(i+1,N):
                if t[i][1] > t[j][1]:
                    tentousuu += 1
        
        answer = min(answer,tentousuu)


    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()))
judge = False
ans = 10**9
for i in range(2**N):
  l = []
  x = 0
  for j in range(N):
    if ((i>>j) & 1):
      l.append([B[j],j,1])
      
    else:
      l.append([A[j],j,0])
  for m in range(N):
    for n in range(N-1,m,-1):
      if l[n][0]<l[n-1][0]:
        l[n],l[n-1]=l[n-1],l[n]
        x+=1

  tmp = True
  for o in range(N):
    if abs(l[o][1]-o)%2==l[o][2]:
      continue
    else:
      if o==N-1:
        tmp = False
        break
      if l[o][0]==l[o+1][0]:
        if abs(l[o+1][1]-o-1)%2!=l[o+1][2]:
          l[o],l[o+1]=l[o+1],l[o]
          continue
      tmp = False
      break
  if tmp:
    judge=True
    ans = min(ans,x)
    
if judge:
  print(ans)
  
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
judge = False
ans = 10**9
for i in range(2**N):
  l = []
  x = 0
  for j in range(N):
    if ((i>>j) & 1):
      l.append((B[j],j,1))
      
    else:
      l.append((A[j],j,0))
  for m in range(N):
    for n in range(N-1,m,-1):
      if l[n][0]<l[n-1][0]:
        l[n],l[n-1]=l[n-1],l[n]
        x+=1

  tmp = True
  for o in range(N):
    if abs(l[o][1]-o)%2==l[o][2]:
      continue
    else:
      if o==N-1:
        tmp = False
        break
      if l[o][0]==l[o+1][0]:
        if abs(l[o+1][1]-o-1)%2!=l[o+1][2]:
          continue
      tmp = False
      break
  if tmp:
    judge=True
    ans = min(ans,x)
    
if judge:
  print(ans)
  
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
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
def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += i-bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

N = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
r = 10**18
for i in range(2**N):
    zs = [0]*N
    for j in range(N):
        if i%2:
            # j と偶数離れたらいい
            zs[j] = (xs[j],(j+1)%2,j)
        else:
            zs[j] = (xs[j],j%2,j)
        i = i>>1
    zs.sort()
    zs2 = [(0, -1)]*N
    ll,rr=0,1
    for l, (z, m, j) in enumerate(zs):
        if m:
            if ll>=N:
                break
            zs2[ll] = (j, z)
            ll += 2
        else:
            if rr>=N:
                break
            zs2[rr] = (j, z)
            rr += 2
    b, ff = 0, 0
    for j, z in zs2:
        if b>z:
            ff = 1
            break
        b = z
    if ff:
        continue
    zs2 = [j+1 for j,_ in zs2]
    r = min(r, tento(zs2))
print(r if r != 10**18 else -1)

#    ff = 0
#    for l, (z, j,m) in enumerate(zs):
#        if (m-l)%2==0: 
#            ff = 1
#            break
#    if ff:
#        continue
#    zs = [j+1 for z,j,m in zs]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
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
def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += i-bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

N = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
for i in range(2**N):
    zs = [0]*N
    for j in range(N):
        if i%2:
            # j と偶数離れたらいい
            zs[j] = (xs[j],(j+1)%2,j)
        else:
            zs[j] = (xs[j],j%2,j)
        i = i>>1
    zs.sort()
    zs2 = [(0, -1)]*N
    ll,rr=0,1
    for l, (z, m, j) in enumerate(zs):
        if m:
            if ll>=N:
                break
            zs2[ll] = (j, z)
            ll += 2
        else:
            if rr>=N:
                break
            zs2[rr] = (j, z)
            rr += 2
    b, ff = 0, 0
    for j, z in zs2:
        if b>z:
            ff = 1
            break
        b = z
    if ff:
        continue
    zs2 = [j+1 for j,_ in zs2]
    print(tento(zs2))

#    ff = 0
#    for l, (z, j,m) in enumerate(zs):
#        if (m-l)%2==0: 
#            ff = 1
#            break
#    if ff:
#        continue
#    zs = [j+1 for z,j,m in zs]

Submission status: Wrong Answer

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

#a = list(map(int, input().split()))

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

dp = [[[999999,[],0] for _ in range(n)] for _ in range(2**n)]
queset = [[0 for _ in range(n)] for _ in range(2**n)]

dp[0][0][0]=0
que = [[0,0]] #[bit, num of right]
done = 0

while(len(que) > done):
    now = que[done]
    done +=1
    nowBits = ValueToBits(now[0],n)
    sumBits = sum(nowBits) # 既に何枚使ったか
    nowTentou = dp[now[0]][now[1]][0]
    nowCards = []
    for i in range(n):
        if(nowBits[i]==1):
            nowCards.append(i)
    nowRight = dp[now[0]][now[1]][2]
    #if(len(nowCards)>0): print(len(nowCards),nowCards[-1],nowRight)
    for i in range(n):
        if(nowBits[i] == 0):
            # 右端に今加えようとしてるカード i は表か裏か
            UpDown = abs(i-sumBits)%2
            # 右端を加えた集合
            nextValue = now[0] + 2**i
            if(queset[nextValue][i]==0):
                que.append([nextValue, i])
                queset[nextValue][i]=1
            #nextCards = list(nowCards)
            #nextCards.append(i)
            nextRight = A[i] if UpDown==0 else B[i]
            #print(nextCards)
            if(nowRight <= nextRight):
                #print(nowRight,nextRight)
                nextTentou = nowTentou
                for k in nowCards:
                    if(k > i):
                        nextTentou+=1
                #print(dp[nextValue][i][0] , nextTentou)
                if(dp[nextValue][i][0] > nextTentou):
                    dp[nextValue][i][0] = nextTentou
                    #dp[nextValue][i][1] = list(nextCards)
                    dp[nextValue][i][2] = nextRight
                    #print(dp[nextValue][i])
#print()
ans=999999
for i in range(n):
    if(ans > dp[2**n-1][i][0]):
        ans = dp[2**n-1][i][0]
if(ans>99998):
    print(-1)
else:
    print(ans)
print(len(que))

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]))
        for i in range(N):
            if abs(num_list[i][2] - i)%2 != num_list[i][1]:
                break
        else:
            move_dist = 0
            for i in range(N):
                for j in range(i+1,N):
                    if num_list[i][2] > num_list[j][2]:
                        move_dist+=1

            answer = min(answer,move_dist)

    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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1


def babble_sort(arr):
    """ バブルソート """
    length = len(arr)
    count=0
    data=[i for i in range(length)]
    swap=[0]*length

    for i in range(length):
        # 3. 走査範囲を前からひとつ狭める
        for j in reversed(range(i+1, length)):
            # 1. 後ろから順に隣り合う要素を比較する。
            if arr[j-1] > arr[j]:
                # 2. 左が右の要素に比べ大きい場合交換する。
                arr[j-1], arr[j] = arr[j], arr[j-1]
                data[j-1], data[j] = data[j], data[j-1]
                swap[data[j]]+=1
                swap[data[j-1]]+=1
                count+=1
    return count,swap

def f(n):
    count=0
    while n:
        count+=n%2
        n//=2
    return count

n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
for bit in range(2**n):
    # if bit==3:
    #     print(f(bit))
    if f(bit)%2!=0:
        continue
    tar=[0]*n
    data=[0]*n
    for i in range(n):
        if (bit>>i & 1):
            tar[i]=B[i]; data[i]=1
        else:
            tar[i]=A[i]
    tmp,swap=babble_sort(tar[:])
    S=[[]]*51
    for i in range(n):
        if swap[i]%2!=data[i]:
            break
    else:
        mans=min(mans,tmp)
    # if bit==3:
    #     print(data,swap,tar,bit,sep="\n")
    # for i in range(n):
    #     if swap[i]%2!=data[i]:
    #         S[tar[i]].append(1)
    #     else:
    #         S[tar[i]].append(0)
            
    # for k in range(51):
    #     for s in range(len(S[k])):
    #         if S[k][s]==1:
    #             for t in range(s+1,len(S[k]),2):
    #                 if S[k][t]==1:
    #                     S[k][s]=S[k][t]=0
    #                     tmp+=t-s
    #                     break
    #             else:
    #                 break

    #             continue
    #     else:
    #         continue
    #     break
    # else:
    #     mans=min(mans,tmp)
    # continue
print(-1 if mans==inf else mans)

Submission status: Wrong Answer

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

N = int(input())

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

odd = []
eve = []
for i in range(N):
    j = i + 1
    if j % 2 == 0:
        eve.append((A[i], i))
        odd.append((B[i], i))
    else:
        eve.append((B[i], i))
        odd.append((A[i], i))

eve.sort()
odd.sort()
memo = {}

ans = 10 ** 6


def dfs(t, bit, L):
    global ans
    if bit == (1 << N) - 1:
        ans = min(ans, memo[L])
    else:
        parity = (len(L) + 1) % 2
        cur = odd if parity else eve
        K = bisect_left(cur, (t, 0))
        for k in range(K, N):
            j = cur[k][1]
            if (bit >> j) & 1 == 0:
                bit2 = bit | (1 << j)
                t2 = cur[k][0]
                L2 = L + str(j)
                inv = 0
                for c in L:
                    if int(c) > j:
                        inv += 1
                if L in memo:
                    memo[L2] = memo[L] + inv
                else:
                    memo[L2] = inv
                dfs(t2, bit2, L2)


dfs(-1, 0, '')
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(), 0)

print(answer if answer < INF else -1)

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):
            for j in range(i+1,N):
                if num_list[i][2] > num_list[j][2]:
                    move_dist+=1

        else: ## 可能な移動である
            answer = min(answer,move_dist)

    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:
#!/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[1]))

        move_dist = 0
        for i in range(N):
            for j in range(i+1,N):
                if num_list[i][2] > num_list[j][2]:
                    move_dist+=1

        else: ## 可能な移動である
            answer = min(answer,move_dist)

    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,=map(int,input().split())
*b,=map(int,input().split())
m=10**18
for i in range(2**n):
    t,u,v=[],[],[]
    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],
            v+=b[j],
        else:
            if j%2:
                u+=a[j],
            else:
                t+=a[j],
            v+=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
    c=0
    for j,p in enumerate(sorted(l)):
        t=v[j]
        if t==p:continue
        for k in range(j+1,n):
            u=v[k]
            v[k]=t
            if p==u:
                c+=k-j
                break
            t=u
    m=min(m,c)
if m==10**18:
    print(-1)
else:
    print(m)