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=[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+0)

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

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
AA=[]
BB=[]
for i in range(n):
    if i%2==0:
        AA.append([A[i],i])
        BB.append([B[i],i])
    else:
        AA.append([B[i],i])
        BB.append([A[i],i])
l=[i for i in range(n)]
ans=-1
for v in itertools.combinations(l,(n+1)//2):
    AAA=[]
    BBB=[]
    c=0
    for i in range(n):
        if c!=(n+1)//2 and i==v[c]:
            AAA.append(AA[i])
            c+=1
        else:
            BBB.append(BB[i])
    AAA=sorted(AAA)
    BBB=sorted(BBB)
    flag=True
    for i in range(n-1):
        if i%2==0:
            if AAA[i//2][0]>BBB[i//2][0]:
                 flag=False
        else:
            if BBB[i//2][0]>AAA[(i+1)//2][0]:
                 flag=False
    if flag:
        ans_=0
        for i in range(len(AAA)):
            ans_+=abs(AAA[i][1]-i*2)
        for i in range(len(BBB)):
            ans_+=abs(BBB[i][1]-i*2-1)
        ans_//=2
        if ans==-1:
            ans=ans_
        else:
            ans=min(ans_,ans)
print(ans)

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 = 0
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 += chk(CCC)
print(ans)

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a

def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]-1]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  x=[]
  for j in range(n):
    if s[j]=="0":x.append([a[j],j,2])
    else:x.append([b[j],j,1])
  x.sort()
  f=False
  for j in range(n):
    if (j+x[j][1]+x[j][2])%2:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1]+1)
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

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):
        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:
import copy
import sys
sys.setrecursionlimit(1 << 20)


def check(array):
    return array == sorted(array)


N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
n = set(range(N - 1))
history = [copy.copy(A)]
h_append = history.append


def dfs(c, i, a, b):
    if c > 0 and a in history:
        return float("inf")
    else:
        h_append(copy.copy(a))
    if check(a):
        return c
    a[i], a[i+1], b[i], b[i+1] = b[i+1], b[i], a[i+1], a[i]
    ret = float("inf")
    for j in n.difference({i}):
        ret = min(ret, dfs(c+1, j, a, b))
    b[i + 1], b[i], a[i + 1], a[i] = a[i], a[i + 1], b[i], b[i + 1]
    return ret


ans = dfs(0, 0, A, B)
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    INF = 10**5

    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):
                if useds[i]: continue
                if p%2 == 0:
                    if (i%2 == 0 and S & (1<<(N-1-i)) == 0) or (i%2 and S & (1<<(N-1-i))):
                        if Cs[i] < minC:
                            minC = Cs[i]
                            iMinC = i
                else:
                    if (i%2 == 0 and S & (1<<(N-1-i))) or (i%2 and S & (1<<(N-1-i)) == 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:
#  --*-coding:utf-8-*--

MAX = 10**9
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

flags = 0

def f(pos, lastVal):
    global flags

    if pos == N:
        return 0

    minCnt = MAX

    for i in range(N):
        bit = 1<<i;

        if flags&bit == 0:
            val = A[i] if (pos-i)%2 == 0 else B[i]
            if val >= lastVal:
                flags ^= bit
                minCnt = min(minCnt, f(pos+1, val) + abs(pos-i))
                flags ^= bit
                         
    return minCnt

ans = f(0, 0)
print(ans//2 if ans < MAX else -1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
    
dic={}
astr=""
bstr=""
for i in range(n):
    astr+=str(a[i]).zfill(2)
    bstr+=str(b[i]).zfill(2)

ab=astr+bstr
dic[ab]=0
d=deque([ab])
# print(d)
import time
t=time.time()
while d:
    if time.time()-t>=1.6:
        print(-1)
        quit()
    tmp=d.popleft()
    # print(tmp)
    for i in range(n-1):
        if int(tmp[i*2:i*2+2])>int(tmp[i*2+2:i*2+4]):
            # print(int(tmp[i*2:i*2+2]),int(tmp[i*2+2:i*2+4]))
            break
    else:
        print(dic[tmp])
        quit()

    for i in range(n-1):
        a=tmp[:n*2]
        b=tmp[n*2:]
        # print(a,b)
        tmp2=a[:i*2]+b[i*2+2:i*2+4]+b[i*2:i*2+2]+a[i*2+4:]+b[:i*2]+a[i*2+2:i*2+4]+a[i*2:i*2+2]+b[i*2+4:]
        # print(tmp2)
        if not tmp2 in dic:
            dic[tmp2]=dic[tmp]+1
            d.append(tmp2)
print(-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
def main():
  Ans=N**2+1
  for bits in range(1<<N):
    C=[A[i] if not (bits>>i)&1 else B[i] for i in range(N)]
    #print(C)
    #org=[A[i] if (bits>>i)&1 else B[i] for i in range(N)]
    cnt=[0 if not((bits>>i)&1) else 1 for i in range(N)]
    #print(C,cnt)
    ans=0
    for i in range(N-1):
      for j in range(N-1,i,-1):
        if C[j]<C[j-1]:
          temp=C[j]
          C[j]=C[j-1]
          C[j-1]=temp
          temp=cnt[j]+1
          cnt[j]=cnt[j-1]+1
          cnt[j-1]=temp
          ans+=1
    #print(C,cnt)
    i=0
    flag=True
    while i<N:
      if cnt[i]%2:
        if i==N-1:
          flag=False
          break
        else:
          if C[i+1]==C[i] and cnt[i+1]%2==1:
            i+=1
            ans+=1
          else:
            flag=False
            break
      i+=1
    if flag:
      Ans=min(ans,Ans)
  if Ans==N**2+1:
    print(-1)
  else:
    print(Ans)
  return
          
main()

Submission status: Wrong Answer

Solution code:
import itertools
import copy

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
Ai=[[] for _ in range(N)]
Bi=[[] for _ in range(N)]

for i in range(N):
    Ai[i]=[A[i],i]
    Bi[i]=[B[i],i]

ans=10**9
for i in range(N//2+1):#青の枚数の取り方
    blue=i*2
    miss=[-1,-1]#失敗したiiとその時の
    for ite in itertools.combinations(range(N), blue):#青の取り方
        cardset=copy.deepcopy(Ai)
        temp=0
        flag=1
        for k in range(len(ite)):#cadset作成
            cardset[ite[k]]=Bi[ite[k]]
        cardset.sort()
        d_odd=0
        d=[0]*N
        for ii in range(N):#1枚ずつ移動判定
            d[ii]=abs(ii-cardset[ii][1])#移動距離
            if d[ii]%2==1:
                d_odd+=1
        if d_odd==blue:
            for ii in range(N):
                if cardset[ii][1] in ite:
                    rb=1#青
                else:
                    rb=0
                if d[ii]%2!=rb:
                    flag=0
                    break
                temp+=d[ii]
            if flag==1:
                ans=min(ans,temp//2)

            
if ans==10**9:
    ans=-1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def int2bit(n):
	ret = [0 for i in range(N)]
	for i in range(N):
		ret[i] = n % 2
		n = n // 2
	return ret

ans = 100000
for n in range(2**N):
	b = int2bit(n)
	if sum(b) % 2 == 1:
		continue
	before = [(A[i], i, 0) if b[i] == 0 else (B[i], i, 1) for i in range(N)]
	used = [False for i in range(N)]
	unused = []
	after = sorted(before)
	I = []
	flag = False
	for i in range(N):
		if flag:
			break
		a = after[i]
		if (i + a[1]) % 2 == a[2] and not used[a[1]]:
			used[a[1]] = True
			I.append(a[1])
		else:
			if not used[a[1]]:
				unused.append(a[1])
			flag2 = False
			for j in unused:
				if (i + j) % 2 == a[2]:
					flag2 = True
					used[j] = True
					unused.remove(j)
					I.append(j)
					break
			if flag2:
				continue
			if i < N-1 and after[i+1][0] != a[0]:
				flag = True
				break
			flag2 = False
			for j in range(a[1], N):
				b = before[j]
				if b[0] != a[0] or used[b[1]]:
					continue
				if (b[1] + i) % 2 == b[2]:
					flag2 = True
					used[b[1]] = True
					I.append(b[1])
					break
			if not flag2:
				flag = True
				break
	if len(I) < N:
		continue
	tmp = 0
	mov = [0 for i in range(N)]
	for i in range(N):
		mov[I[i]] = i
	for i in range(N-1):
		for j in range(i+1, N):
			if mov[i] > mov[j]:
				tmp += 1
	ans = min(ans, tmp)
if ans < 100000:
	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()))


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


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
        print(cnt)
        break
    if i == n-1 and f:
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 20)


def check(array):
    return array == sorted(array)


N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
n = set(range(N - 1))
history = [A]
h_append = history.append


def dfs(c, i, a, b):
    if c > 0 and a in history:
        return float("inf")
    else:
        h_append(a)
    if check(a):
        return c
    a[i], a[i+1], b[i], b[i+1] = b[i+1], b[i], a[i+1], a[i]
    ret = float("inf")
    for j in n.difference({i}):
        ret = min(ret, dfs(c+1, j, a, b))
    b[i + 1], b[i], a[i + 1], a[i] = a[i], a[i + 1], b[i], b[i + 1]
    return ret


ans = dfs(0, 0, A, B)
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    INF = 10**5

    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):
                if useds[i]: continue
                if p%2 == 0:
                    if (i%2 == 0 and S & (1<<(N-1-i)) == 0) or (i%2 and S & (1<<(N-1-i))):
                        if Cs[i] < minC:
                            minC = Cs[i]
                            iMinC = i
                else:
                    if (i%2 == 0 and S & (1<<(N-1-i))) or (i%2 and S & (1<<(N-1-i)) == 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:
#!/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=[0]*51
    # if bit==3:
    #     print(data,swap,tar,bit,sep="\n")
    for i in range(n):
        if swap[i]%2!=data[i]:
        #     if S[tar[i]]:
        #         S[tar[i]]=0
        #     else:
        #         S[tar[i]]=1
        # elif S[tar[i]]:
            break
    else:
        mans=min(mans,tmp)
    continue
print(-1 if mans==inf else mans)

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, min(N, (i+1)*2)):
        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:
def examA():
    H = I()
    W = I()
    N = I()
    ans = (N-1)//max(H,W) + 1
    print(ans)
    return

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

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

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

def examE():
    return

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

if __name__ == '__main__':
    examD()


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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

        ans_new = 0
        for i in range(N):
            for j in range(i+1, N):
                if tmp[i] > tmp[j]:
                    ans_new += 1
        # print(v, tmp, ans_new, odd, even)
        ans = min(ans, ans_new)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import time
n = int(input())
red = list(map(int,input().split()))
blue = list(map(int,input().split()))
  # start = time.time()
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()
    nu = 0
    for h in range(n):
        nu += abs(num[h][-1] - h)
        if (num[h][1] - h) % 2 != 0:
            break
        if h == n - 1:
  #            print(num)
            ans = min(ans, nu // 2)
  #real_time = time.time()-start
  #print(real_time)
if ans == 10 ** 5:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

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

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

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

def examE():
    return

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

if __name__ == '__main__':
    examD()


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

Submission status: Wrong Answer

Solution code:
n=int(input())
ar=[]
aa=list(map(int,input().split()))
bb=list(map(int,input().split()))
for i in range(n):
    ar.append((aa[i],bb[i]))

inf=n*n*n*n

dp=[ [ [-1 for k in range(1<<(n+1))] for j in range(2) ] for i in range(n+1) ]

def func(idx,s,mask):
    if mask==(1<<n)-1:
        return 0
    
    if(dp[idx][s][mask]==-1):
        ans=inf
        count=0
        for i in range(n):
            if mask&(1<<i)!=0:
                count+=1
        for i in range(n):
            if mask&(1<<i)==0:
                cost=0
                if i>count:
                    cost=i-count
                val=-inf
                if count>0:
                    val=ar[idx][s]
                ss=abs(i-count)%2
                myval=ar[i][ss]
                if val<=myval:
                    ans=min(ans,cost+func(i,ss,mask|(1<<i)))
        dp[idx][s][mask]=ans
    return dp[idx][s][mask]

ans=func(n-1,0,0)
if ans>=inf:
    ans=-1
print(ans)