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()))
INF = 10**18
AB = [A, B]

dp = [[INF] * 51 for _ in range(1 << N)]
dp[0][0] = 0

for state in range(1 << N):
    size = 0
    for i in range(N):
        if (state & (1 << i)) > 0:
            size += 1

    S = []
    now = size
    for i in range(N):
        if (state & (1 << i)) == 0:
            S.append((i, now))
            now += 1

    for s in range(51):
        for i, now in S:
            val = AB[(i - size) % 2][i]
            d = dp[state][s] + abs(now - size)
            if val >= s and dp[state | (1 << i)][val] < d:
                dp[state | (1 << i)][val] = d

ans = min(dp[(1 << N) - 1])
print(ans if ans < INF else -1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
INF = 10**18
AB = [A, B]

ans = INF
for state in range(1 << N):
    V = []
    cnt0 = [0] * 51
    cnt1 = [0] * 51
    for i in range(N):
        isRed = 0 if (state & (1 << i)) != 0 else 1
        c = AB[isRed][i]

        V.append((c, i))
        if (i % 2 == 0) ^ isRed:
            cnt0[c] += 1
        else:
            cnt1[c] += 1

    V.sort()
    for i, (v, _) in enumerate(V):
        if i % 2 == 0:
            cnt0[v] -= 1
        else:
            cnt1[v] -= 1
    if not all(c == 0 for c in cnt0 + cnt1):
        continue

    cnt = 0
    V = [i for _, i in V]
    for i, v in enumerate(V):
        for j in V[:i]:
            if j > v:
                cnt += 1
    ans = min(ans, cnt)

print(ans if ans < INF else -1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
allpat=[]
todo=[[]]
while todo:
  pat=todo.pop()
  if len(pat)==n//2:
    allpat.append(pat)
    continue
  s=0
  if pat:s=max(pat)+1
  for i in range(s,n):
    todo.append(pat+[i])

def func(pat):
  # カードを最終的に偶奇どちらのidxになるかで分類
  # pat内のidxが最後に奇数のidxになるとする
  ablev=[]
  ablod=[]
  for i in range(n):
    if i in pat:
      if i%2==0:
        ablod.append([i,b[i]])
      else:
        ablod.append([i,a[i]])
    else:
      if i%2==0:
        ablev.append([i,a[i]])
      else:
        ablev.append([i,b[i]])
  ablev.sort(key=lambda x:x[1]*20+x[0])
  ablod.sort(key=lambda x:x[1]*20+x[0])
  now=0
  ret=0
  for i in range(n//2):
    if ablev[i][1]>=now:
      now=ablev[i][1]
      ret+=abs(2*i-ablev[i][0])
    else:
      return -1
    if ablod[i][1]>=now:
      now=ablod[i][1]
      ret+=abs(2*i+1-ablod[i][0])
    else:
      return -1
  if n%2==1:
    if ablev[n//2][1]>=now:
      now=ablev[i][1]
      ret+=abs(n-1-ablev[i][0])
    else:
      return -1
  return ret//2

ans=float('inf')
for pat in allpat:
  t=func(pat)
  if t>=0:
    ans=min(ans,t)
print(ans if ans!=float('inf') else -1)
#print(*allpat,sep='\n')

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def popcnt(n):
    return bin(n).count("1")

def main():
    n = int(ipt())
    card = [[int(i) for i in ipt().split()] for _ in range(2)]
#    n = 18
#    card = [[j*500-i*3+400 for j in range(18)] for i in range(2)]
    dp = [[10**18]*n for i in range(2**n)]

    for i in range(1,2**n):
        pi = popcnt(i)
        if pi == 1:
            for j in range(n):
                if (i>>j)&1:
                    dp[i][j] = 0
        else:
            pp = 0
            for j in range(n-1,-1,-1):
                if (i>>j)&1:
                    nn = card[(pi-j+1)%2][j]
                    pn = i-2**j
                    dpn = dp[pn]
                    dpij = dp[i][j]
                    for k in range(n):
                        if dpij > dpn[k]+pp:
    #                        print(k,card[(pi-k)%2][k],nn)
                            if card[(pi-k)%2][k] <= nn:
                                dp[i][j] = dpn[k]+pp
                    pp += 1
    ans = min(dp[2**n-1])
    if ans == 10**18:
        ans = -1
    print(ans)
    return None

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

dp = [[100100] * (1 << N) for _ in range(18)]
for i in range(N):
    dp[i][1 << i] = i 
for mask in range(1, 1 << N):
    mask_pop = format(mask, 'b').count('1')
    for j in range(N):
        if (1 << j) & mask:
            prev_mask = mask & ~(1 << j)
            cost_delta = format(prev_mask & (-1 << j), 'b').count('1')
            if (j - mask_pop) % 2 == 0:
                for t in range(N):
                    last_elem = A[t] if (t - mask_pop - 1) % 2 == 0 else B[t]
                    if last_elem <= A[j]:
                        if dp[j][mask] > dp[t][prev_mask] + cost_delta:
                            dp[j][mask] = dp[t][prev_mask] + cost_delta
            else: 
                for t in range(N):
                    last_elem = A[t] if (t - mask_pop) % 2 else B[t]
                    if last_elem <= B[j]:
                        if dp[j][mask] > dp[t][prev_mask] + cost_delta:
                            dp[j][mask] = dp[t][prev_mask] + cost_delta

ans = min((dp[i][-1] for i in range(N)))
if ans == 100100:
    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()))

not_used = {i for i in range(N)}
def solve(index, cur_elem, cost, cur_min):
    global not_used
    # print(" " * index, cur_elem, cost, cur_min)
    for i in not_used:
        if (index - i) % 2 == 0:
            if A[i] >= cur_elem:
                cost_delta = 0
                for j in range(i, N):
                    if j not in not_used:
                        cost_delta += 1
                new_cost = cost + cost_delta
                if new_cost < cur_min:
                    if index + 1 == N:
                        cur_min = min(cur_min, new_cost)
                    else:
                        not_used.discard(i)
                        cur_min = min(cur_min, solve(index + 1, A[i], new_cost, cur_min))
                        not_used.add(i)
        else:
            if B[i] >= cur_elem:
                cost_delta = 0
                for j in range(i, N):
                    if j not in not_used:
                        cost_delta += 1
                new_cost = cost + cost_delta
                if new_cost < cur_min:
                    if index + 1 == N:
                        cur_min = min(cur_min, new_cost)
                    else:
                        not_used.discard(i)
                        cur_min = min(cur_min, solve(index + 1, B[i], new_cost, cur_min))
                        not_used.add(i)
    return cur_min

ans = solve(0, -1, 0, 100000)
if ans == 100000:
    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()))

def solve(not_used, index, cur_elem, cost, cur_min):
    #print("\t" * index, cur_elem, cost)
    if index == N:
        return cost
    for i in not_used:
        if (index - i) % 2 == 0:
            if A[i] >= cur_elem:
                new_cost = cost + abs(i - index)
                if new_cost < cur_min:
                    cur_min = min(cur_min, solve(not_used - {i}, index + 1, A[i], new_cost, cur_min))
        else:
            if B[i] >= cur_elem:
                new_cost = cost + abs(i - index)
                if new_cost < cur_min:
                    cur_min = min(cur_min, solve(not_used - {i}, index + 1, B[i], new_cost, cur_min))
    return cur_min

ans = solve({i for i in range(N)}, 0, -1, 0, 100000)
if ans == 100000:
    print(-1)
else:
    print(ans // 2)

Submission status: Wrong Answer

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

ans = 10**10
for i in range(2**N):
    b = bin(i)[2:]
    F = list(map(int,b.zfill(N))) # 1:A, 0:B
    if (F.count(0) % 2) == 1:
        continue
    C = [a if f else b for a,b,f in zip(A,B,F)]
    S = sorted(C)
    V = list(set(C))
    rB = [b for f,b in zip(F,B) if not f]
    for v in V:
        iC = [i for i,c in enumerate(C) if c == v]
        iS = [i for i,s in enumerate(S) if s == v]
        iB = [i for i,(f,b) in enumerate(zip(F,B)) if b == v and not f]
        if (sum(iC) + sum(iS)) % 2 != len(iB) % 2:
            break
    else: # not break
        p = 0
        for i in range(N):
            for j in range(i):
                if C[i]<C[j]:
                    p += 1
        if p < ans:
            #print(F,C)
            ans = p

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

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 10 ** 15
for i in range(2 ** N):
  C = [0] * N
  D = [0] * N#reversed
  count = 0
  for j in range(N):
    if (i >> j) & 1:
      C[j] = B[j]
      D[j] = 1
      count += 1
    else:
      C[j] = A[j]
    
  if count % 2 != 0:
      continue
  else:
      C2 = sorted(C)
      #print(C, C2, D, count)
      bad = 0 
      for k in range(N):
        if (C[k] != C2[k]) and (D[k] == 0):
          bad = 1
        if (C[k] == C2[k]) and (D[k] == 1):
          bad = 1
      if bad == 0:
        ans = min(ans, int(count // 2))

if ans < 10 ** 15:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:


n = int(raw_input())
ais,bis = map(int, raw_input().split()), map(int, raw_input().split())

def dfs(i, ais, example):
	if i == len(ais):
		
		return 0

	if ais[i] == example[i]:
		return dfs(i+1, ais, example)
	else:
		for j in range(i + 1, len(ais)):
			if example[i] == ais[j]:
				return j-i + dfs(i+1, ais[:i] + [ais[j]] + ais[i:j] + ais[j+1:], example)

   
m = +float('inf')
t = dfs(0,ais, sorted(ais))
if not(t % 2 == 0):  t = float('inf')

m = min(m, t)
t = dfs(0,bis, sorted(bis)) 

if not(t % 2 == 1): t = float('inf')
m = min(m, t)
print m if m < float('inf') else -1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def check_increasing(L):
        for i in range(1, n):
            if L[i][1] < L[i-1][1]:
                return False
        return True


    def modified_merge(left, right):
        '''
        ソート済み配列 left, right を受け取り、 O(n) で全体のソート済み配列を生成する
        マージの過程で転倒数をメモして返す

        >>> modified_merge([1, 5, 7], [2, 3, 3])
        (6, [1, 2, 3, 3, 5, 7])

        Args:
            left (list)
            right (list)
        Returns:
            inv (int)
            sorted_list (list)
        '''
        sorted_list = []
        i, j, inv = 0, 0, 0
        buf_1 = left[:] + [float('inf')]
        buf_2 = right[:] + [float('inf')]
        for _ in range(len(left) + len(right)):
            if buf_1[i] < buf_2[j]:
                sorted_list.append(buf_1[i])
                i += 1
                inv += j
            else:
                sorted_list.append(buf_2[j])
                j += 1
        return inv, sorted_list


    def modified_merge_sort(L, i, j):
        '''
        [i, j), つまりL[i:j] を O(nlgn) で非破壊的かつ安定にマージソートする
        マージソートの過程で転倒数をメモして返す
        
        >>> modified_merge_sort([3, 5, 2, 1, 0], 0, 5)
        (9, [0, 1, 2, 3, 5])

        Args:
            L (list)
            i (int)
            j (int)
        Returns:
            inv (int)
            sorted_list (list)
        '''
        if i + 1 == j:
            # L[i:j+1] = [L[i]]
            return 0, [L[i]]
        mid = (i + j) // 2
        left_inv_cnt, left = modified_merge_sort(L, i, mid)
        right_inv_cnt, right = modified_merge_sort(L, mid, j)
        merge_inv_cnt, sorted_list = modified_merge(left, right)
        return left_inv_cnt + right_inv_cnt + merge_inv_cnt, sorted_list


    def count_inversion(L):
        '''
        O(nlgn) で L の要素の転倒数を求める

        >>> count_inversion([1, 9, 2, 7, 5, 6, 4, 8, 3, 0])
        26
        '''
        cnt, _ = modified_merge_sort(L, 0, len(L))
        return cnt


    def calc_swapflip(L):
        return count_inversion(list(map(lambda x: x[0], L)))

    
    n = ii()
    A = lmi()
    B = lmi()

    ans = inf

    w = [(i, A[i], B[i]) if i % 2 == 0 else (i, B[i], A[i]) for i in range(n)]
    w.sort(key=itemgetter(1))

    for pattern in combinations(w, r=(n+1)//2):
        # print(pattern)
        left = [(elm[0], elm[2], elm[1]) for elm in w if elm not in pattern]
        left.sort(key=itemgetter(1))
        concat = []
        for i in range(n//2):
            concat.append(pattern[i])
            concat.append(left[i])
        if n % 2 == 1:
            concat.append(pattern[-1])
        # print(concat)
        if check_increasing(concat):
            ans = min(ans, calc_swapflip(concat))
        # print(ans)
    
    print(ans) if ans != inf else print(-1)
        




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
nums = [None]*n

# def groupby(l):
#     """l : list of tuple
#     tuple[0]で分割する
#     """
#     if len(l)==0:
#         pass
#     else:
        
#         yield

def pp(func):
    def wrapped(*args, **keys):
        print(args, keys)
        val = func(*args, **keys)
        print(val)
        return val
    return wrapped

# @pp
def sub(fr, to, bb):
    # frをtoのいずれかに対応付ける
    elist = []
    olist = []
    for ff,bbb in zip(fr, bb):
        if (ff+bbb)%2:
            olist.append(ff)
        else:
            elist.append(ff)

    elist2 = []
    olist2 = []
    for item in to:
        if item%2:
            olist2.append(item)
        else:
            elist2.append(item)
    if len(olist2)==len(olist) and len(elist2)==len(elist):
        olist.sort()
        elist.sort()
        return sum(abs(o1-o2) for o1,o2 in zip(olist, olist2)) + sum(abs(e1-e2) for e1, e2 in zip(elist, elist2))
    else:
        return None
    
#     if sum((ff-tt-bbb)%2 for ff,tt,bbb in zip(fr, to, bb)):
#         return None
    
    
best = 10**9
for bit in range(1<<n):
    for i in range(n):
        val = b[i] if bit>>i&1 else a[i]
        nums[i] = (val, i, bit>>i&1)
    nums.sort()
    prev, fr, bb = nums[0]
    to = [0]
    fr = [fr]
    bb = [bb]
    valid = True
    ans = 0
    for i in range(1,n):
        cv, cfr, cbb = nums[i]
        if prev!=cv:
            res = sub(fr, to, bb)
            if res is None:
                valid = False
                break
            ans += res
            prev, fr, bb = cv, [cfr], [cbb]
            to = [i]
        else:
            fr.append(cfr)
            to.append(i)
            bb.append(cbb)
    else:
        res = sub(fr, to, bb)
        if res is None:
            valid = False
        else:
            ans += res
    if valid:
        best = min(best, ans)
#         print(nums, ans)
if best==10**9:
    print(-1)
else:
    print(best//2)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
nums = [None]*n

# def groupby(l):
#     """l : list of tuple
#     tuple[0]で分割する
#     """
#     if len(l)==0:
#         pass
#     else:
        
#         yield

def pp(func):
    def wrapped(*args, **keys):
        print(args, keys)
        val = func(*args, **keys)
        print(val)
        return val
    return wrapped

# @pp
def sub(fr, to, bb):
    # frをtoのいずれかに対応付ける
    elist = []
    olist = []
    for ff,bbb in zip(fr, bb):
        if (ff+bbb)%2:
            olist.append(ff)
        else:
            elist.append(ff)
    elist2 = []
    olist2 = []
    for item in to:
        if item%2:
            olist2.append(item)
        else:
            elist2.append(item)
    if len(olist2)==len(olist) and len(elist2)==len(elist):
        return sum(abs(o1-o2) for o1,o2 in zip(olist, olist2)) + sum(abs(e1-e2) for e1, e2 in zip(elist, elist2))
    else:
        return None
    
#     if sum((ff-tt-bbb)%2 for ff,tt,bbb in zip(fr, to, bb)):
#         return None
    
    
best = 10**9
for bit in range(1<<n):
    for i in range(n):
        val = b[i] if bit>>i&1 else a[i]
        nums[i] = (val, i, bit>>i&1)
    nums.sort()
    prev, fr, bb = nums[0]
    to = [0]
    fr = [fr]
    bb = [bb]
    valid = True
    ans = 0
    for i in range(1,n):
        cv, cfr, cbb = nums[i]
        if prev!=cv:
            res = sub(fr, to, bb)
            if res is None:
                valid = False
                break
            ans += res
            prev, fr, bb = cv, [cfr], [cbb]
            to = [i]
        else:
            fr.append(cfr)
            to.append(i)
            bb.append(cbb)
    else:
        res = sub(fr, to, bb)
        if res is None:
            valid = False
        else:
            ans += res
    if valid:
        best = min(best, ans)
#         print(nums, ans)
if best==10**9:
    print(-1)
else:
    print(best//2)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from itertools import permutations,combinations
sys.setrecursionlimit(10 ** 7)

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

# 全探索
INF = 10 ** 5
answer = INF
N = ir()
if N == 1:
    print(0); exit()
A = lr()
B = lr()
for pattern in combinations(range(N), (N+1)//2):
    pattern = set(pattern)
    red = []
    blue = []
    for i in range(N):
        if i in pattern:
            red.append((B[i], i) if i&1 else (A[i], i))
        else:
            blue.append((A[i], i) if i&1 else (B[i], i))
    red.sort()
    blue.sort()
    result = []
    for i in range(N//2):
        if red[i][0] > blue[i][0]:
            break
        if i + 1 < len(red) and red[i+1] < blue[i]:
            break
        result.append(red[i][1])
        result.append(blue[i][1])
    else:
        if N&1 and blue[-1][0] > red[-1][0]:
            continue
        if N&1:
            result.append(red[-1][1])
        temp = 0
        used = set()
        for i in range(N):
            for x in used:
                if result[i] < x:
                    temp += 1
            used.add(result[i])            
        if temp < answer:
            answer = temp

print(answer if answer != INF else -1)
# 12

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from itertools import permutations,combinations
sys.setrecursionlimit(10 ** 7)

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

# 全探索
INF = 10 ** 5
answer = INF
N = ir()
if N == 1:
    print(0); exit()
A = lr()
B = lr()
for pattern in combinations(range(N), (N+1)//2):
    pattern = set(pattern)
    red = []
    blue = []
    for i in range(N):
        if i in pattern:
            red.append((B[i], i) if i&1 else (A[i], i))
        else:
            blue.append((A[i], i) if i&1 else (B[i], i))
    red.sort()
    blue.sort()
    temp = 0
    for i in range(N//2):
        if red[i][0] > blue[i][0]:
            break
        if i + 1 < len(red) and red[i+1] < blue[i]:
            break
        temp += abs(red[i][1] - 2 * i)
        temp += abs(blue[i][1] - (2 * i + 1))
    else:
        if N&1 and blue[-1][0] > red[-1][0]:
            continue
        temp //= 2
        if temp < answer:
            answer = temp

print(answer if answer != INF else -1)
# 12