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: Accepted

Solution code:
#This function merges two sorted arrays and returns inversion count in the arrays.*/ 
def merge(arr, temp, left, mid, right): 
    inv_count = 0
  
    i = left #i is index for left subarray*/ 
    j = mid #i is index for right subarray*/ 
    k = left #i is index for resultant merged subarray*/ 
    while ((i <= mid - 1) and (j <= right)): 
        if (arr[i] <= arr[j]): 
            temp[k] = arr[i] 
            k += 1
            i += 1
        else: 
            temp[k] = arr[j] 
            k += 1
            j += 1
  
            #this is tricky -- see above explanation/ 
            # diagram for merge()*/ 
            inv_count = inv_count + (mid - i) 
  
    #Copy the remaining elements of left subarray 
    # (if there are any) to temp*/ 
    while (i <= mid - 1): 
        temp[k] = arr[i] 
        k += 1
        i += 1
  
    #Copy the remaining elements of right subarray 
    # (if there are any) to temp*/ 
    while (j <= right): 
        temp[k] = arr[j] 
        k += 1
        j += 1
  
    # Copy back the merged elements to original array*/ 
    for i in range(left,right+1,1): 
        arr[i] = temp[i] 
  
    return inv_count 
  
#An auxiliary recursive function that sorts the input 
# array and returns the number of inversions in the 
# array. */ 
def _mergeSort(arr, temp, left, right): 
    inv_count = 0
    if (right > left): 
        # Divide the array into two parts and call 
        #_mergeSortAndCountInv() 
        # for each of the parts */ 
        mid = int((right + left)/2) 
  
        #Inversion count will be sum of inversions in 
        # left-part, right-part and number of inversions 
        # in merging */ 
        inv_count = _mergeSort(arr, temp, left, mid) 
        inv_count += _mergeSort(arr, temp, mid+1, right) 
  
        # Merge the two parts*/ 
        inv_count += merge(arr, temp, left, mid+1, right) 
  
    return inv_count 
  
#This function sorts the input array and returns the 
#number of inversions in the array */ 
def countSwaps(arr, n): 
    temp = [0 for i in range(n)] 
    return _mergeSort(arr, temp, 0, n - 1) 


from itertools import combinations, zip_longest

N = int(input())

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

cards = [(a,b) if i % 2 == 0 else (b,a) for i,(a,b) in enumerate(zip(A,B))]

best = float('inf')

for odd_indices in combinations(range(N), N//2):
    odds = sorted((cards[i][1], i) for i in odd_indices)
    evens = sorted((card[0], i) for i,card in enumerate(cards) if i not in odd_indices)


    union = []
    for e,o in zip_longest(evens,odds):
        union.append(e)
        if o is not None:
            union.append(o)
    if all(a <= b for (a,_),(b,_) in zip(union,union[1:])):
        indices = [i for _,i in union]
        best = min(best, countSwaps(indices, N))

if best == float('inf'):
    print(-1)
else:
    print(best)

Submission status: Accepted

Solution code:
from itertools import combinations

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

ret = float('inf')
for ce in combinations(range(N), (N + 1) // 2) :
  e, o = [], []
  for i in range(N) :
    if i in ce :
      if i % 2 == 0 :
        e.append([A[i], i])
      else :
        e.append([B[i], i])
    else :
      if i % 2 == 0 :
        o.append([B[i], i])
      else :
        o.append([A[i], i])
  
  e.sort()
  o.sort()
  s = []
  for i in range(N // 2) :
    s.append(e[i])
    s.append(o[i])
  if N % 2 != 0 :
    s.append(e[N // 2])
  
  for i in range(1, N) :
    if s[i][0] < s[i-1][0] :
      break
    
  else :
    tmp = 0
    for i in range(N) :
      for j in range(i) :
        if s[j][1] > s[i][1] :
          tmp += 1
    ret = min(ret, tmp)
    
if ret == float('inf') :
  print(-1)
else :
  print(ret)

Submission status: Accepted

Solution code:
from itertools import *
def count_inversion(sequence):
    return sum(sum(m<n for m in sequence[i+1:]) for i,n in enumerate(sequence))

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

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

up.sort()
l = set([i for i in range(n)])

ans = 10000
for u in combinations(up, (n+1)//2):
    index = []
    value = []
    for val, ind in u:
        index.append(ind)
        value.append(val)

    d_index = l - set(index)
    d = []
    for i in d_index:
        d.append(down[i])
    d.sort()
    value.append(100)
    flag = 1
    for i in range(len(d)):
        if not value[i] <= d[i][0] <= value[i+1]:
            flag = 0
            break
    if flag == 0:
        continue

    for i in range(len(d)):
        index.insert(2*i+1, d[i][1])

    ans = min(ans, count_inversion(index))



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

Submission status: Accepted

Solution code:
# instead of AVLTree
class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    # 0からiまでの区間和
    # 立っているビットを下から処理
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # i番目の要素にxを足す
    # 覆ってる区間すべてに足す
    def add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)
    
    def length(self):
        return self.query_sum(self.max)
    
    # 下からc番目(0-indexed)の数
    # O(log(N))
    def search(self, c):
        c += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < c:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max:
            return False
        return ind + 1
    
    def bisect_right(self, x):
        return self.query_sum(x)

    def bisect_left(self, x):
        if x == 1:
            return 0
        return self.query_sum(x-1)

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()

import sys
input = sys.stdin.readline
from operator import itemgetter

INF = 10**15

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

for i in range(N):
    if i%2 == 1:
        a = A[i]
        A[i] = B[i]
        B[i] = a

INDs = []
def dfs(p,L):
    if p == N:
        if len(L) == (N+1)//2:
            INDs.append(L)
        return
    dfs(p+1, L+[p])
    dfs(p+1, L)
    return

dfs(0, [])

ans = INF
for IND in INDs:
    As = []
    Bs = []
    usingA = [False]*N
    for ind in IND:
        usingA[ind] = True
    for ind in range(N):
        if usingA[ind]:
            As.append((A[ind], ind))
        else:
            Bs.append((B[ind], ind))
    As.sort()
    Bs.sort()
    ok = True
    pre = -INF
    Array = [None]*N
    for i in range(N):
        if i%2 == 0:
            if As[i//2][0] < pre:
                ok = False
                break
            Array[As[i//2][1]] = i+1
            pre = As[i//2][0]
        else:
            if Bs[i//2][0] < pre:
                ok = False
                break
            Array[Bs[i//2][1]] = i+1
            pre = Bs[i//2][0]
    if not ok:
        continue
    
    bit = BITbisect(N)
    nowans = 0
    for j, a in enumerate(Array):
        nowans += j - bit.query_sum(a)
        bit.add(a, 1)
    
    if nowans < ans:
        ans = nowans

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

Submission status: Accepted

Solution code:
import itertools
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

# 2**18 == 262144
N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


# 18C9 < 50000
# どれを偶数番目にするか決まれば回数も分かる
ans = INF
for evens_i in itertools.combinations(range(N), r=(N + 1) // 2):
    is_even = [False] * N
    for i in evens_i:
        is_even[i] = True
    evens = []
    odds = []
    for i, even in enumerate(is_even):
        if even:
            evens.append((A[i] if i % 2 == 0 else B[i], i))
        else:
            odds.append((A[i] if i % 2 == 1 else B[i], i))
    evens.sort()
    odds.sort()

    prev = -1
    # 転倒数
    bit = BinaryIndexedTree(size=N)
    ok = True
    cnt = 0
    for i in range(N):
        c, mi = [evens, odds][i % 2][i // 2]
        if c < prev:
            ok = False
            break
        prev = c
        cnt += i - bit.sum(mi)
        bit.add(mi, 1)
    if ok:
        ans = min(ans, cnt)
        # print(evens_i, cnt, evens, odds)
if ans == INF:
    print(-1)
else:
    print(int(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

UP=(N+1)//2
DOWN=N-UP

ANS=1<<31

def ten(A):
    LEN=len(A)
    MAX=max(A)
    MIN=min(A)

    BIT=[0]*(MAX-MIN+2)# 出現回数をbit indexed treeの形でもっておく.

    def update(v,w):# index vにwを加える
        while v<=MAX-MIN+1:
            BIT[v]+=w
            v+=(v&(-v))# 自分を含む大きなノードへ. たとえばv=3→v=4

    def getvalue(v):# MIN～vの区間の和を求める
        ANS=0
        while v!=0:
            ANS+=BIT[v]
            v-=(v&(-v))# たとえばv=3→v=2へ
        return ANS

    ANS=0        
    for i in range(LEN):# A[0],A[1],...とBITを更新しながら,各A[i]について転倒数を求める.
        bit_ai=A[i]-MIN+1# A[i]がBITの中で何番目か

        ANS+=i# 今まで出現した個数.
        ANS-=getvalue(bit_ai)# 今まで出現した中で,MIN～bit_aiの個数を減らす.
        # bit_ai～MAXの出現個数が転倒数

        update(bit_ai,1)

    return ANS
    

for i in range(1<<N):
    UD=[0,0]
    S0=[]
    S1=[]

    for j in range(N):
        if (1<<j) & i !=0:
            if j%2==0:
                S0.append((A[j],j))
            else:
                S1.append((A[j],j))
            UD[j%2]+=1

        else:
            if (j+1)%2==0:
                S0.append((B[j],j))
            else:
                S1.append((B[j],j))
                
            UD[(j+1)%2]+=1

    if UD[0]==UP and UD[1]==DOWN:
        S0.sort()
        S1.sort()
        #print(UD,S0,S1)

        for i in range(1,N):
            if i%2==0:
                if S0[i//2][0]>=S1[(i-1)//2][0]:
                    True
                else:
                    break
            else:
                if S1[i//2][0]>=S0[(i-1)//2][0]:
                    True
                else:
                    break
        else:
            K=[]
            for i in range(N):
                if i%2==0:
                    K.append(S0[i//2][1])
                else:
                    K.append(S1[i//2][1])

            #print(K)
            #print(ten(K))

            ANS=min(ANS,ten(K))

if ANS==1<<31:
    print(-1)
else:
    print(ANS)

Submission status: Accepted

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

A = [A,B]

import itertools

C = list(itertools.combinations([i for i in range(n)], n//2))
D = [[0] * 2 for i in range(n)]


def sw(G):
    a = 0
    # print("G",G)
    for i in range(len(G)):
        j = i
        while G[j] != i:
            j += 1
        for k in range(j, i, -1):
            ss = G[k]
            G[k] = G[k-1]
            G[k-1] = ss
            a += 1
            # print(G)
    # print(a)
    return a

ans = float("inf")

for i in range(len(C)):
    D = [[0] * 2 for i in range(n//2)]
    E = [[0] * 2 for i in range(n - n//2)]
    L = [0] * n
    for k in range(len(C[i])):
        D[k][0] = A[(C[i][k]+1)%2][C[i][k]]
        D[k][1] = C[i][k]
        L[C[i][k]] = 1
    l = 0
    for k in range(n):
        if L[k] == 0:
            E[l][0] = A[k%2][k]
            E[l][1] = k
            l += 1
    D.sort(key=lambda x:x[1])
    D.sort()
    E.sort(key=lambda x:x[1])
    E.sort()
    F = []
    for i in range(n):
        if i % 2 == 0:
            F.append(E[i//2])
        else:
            F.append(D[i//2])
    # print(F)
    ok = 1
    for i in range(len(F)-1):
        if F[i][0] > F[i+1][0]:
            ok = 0
    # print("ok",ok)
    if ok == 1:
        ans0 = sw([F[i][1] for i in range(n)])
        ans = min(ans, ans0)
    
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = 10**10
for bit in range(1<<n):
  l = a[:]
  rev = [0]*n
  for i in range(n):
    if bit & 1<<i:
      rev[i] = 1
      l[i] = b[i]
  if sum(rev) % 2:
    continue
  odd = list()
  even = list()
  for i in range(n):
    if rev[i]^(i&1):
      even.append((l[i],i))
    else:
      odd.append((l[i],i))
  if len(even) != n//2:
    continue
  odd.sort()
  even.sort()
  l = list()
  for x,y in zip(odd,even):
    l.append(x)
    l.append(y)
  if n&1: l.append(odd[-1])
  fl = 0
  for x,y in zip(l,l[1:]):
    if x[0] > y[0]:
      fl = 1
      break
  if fl: continue
  f = [x[1] for x in l]
  # print('ok', bit, even, odd)
  cnt = 0
  g = [0]*n
  for x in f:
    cnt += sum(g[x:])
    g[x] = 1
  if ans > cnt:
    ans = cnt
if ans > 10**9:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:

def solve() : 
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    m = 1<<n
    dp = [[10000 for i in range(n)] for i in range(m)]
    for i in range(n) :
        dp[1<<i][i]=0
    for i in range(m) :
        c = 0
        for j in range(n) :
            if (1<<j)&i != 0 : c += 1
        cnt = c
        for j in range(n) :
            if (1<<j)&i == 0 : continue
            cnt -= 1
            pre = i - (1<<j)
            for k in range(n) :
                if (1<<k) & i == 0 : continue
                cur = (b[k] if (c-k)%2 == 1 else a[k])
                nxt = (a[j] if (c-j)%2 == 1 else b[j])
                if cur <= nxt : dp[i][j]=min(dp[i][j],dp[pre][k]+cnt)
    ans = 10000
    for i in range(n) :
        ans = min(ans,dp[m-1][i])
    print(ans if ans != 10000 else -1)
solve()

Submission status: Runtime Error

Solution code:

Submission status: Runtime Error

Solution code:


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

mem = {}
def dfs(ais, bis):
	if all([ais[ii] <= ais[ii+1] for ii in range(len(ais)-1)]):
		return (True, 0)
	mem[tuple(ais)+tuple(bis)] = True
	m = +float('inf')
	flag = False
	for i in range(len(ais)-1):
		nais = ais[:i] +bis[i:i+2] + ais[i+2:]
		nbis = bis[:i] +ais[i:i+2] + bis[i+2:]
   		
   		if tuple(nais)+tuple(nbis) not in mem:
   			mem[tuple(nais)+tuple(nbis)] = True
	   		flag, steps = dfs(nais, nbis) 
   		if flag:
   			flag = True
   			m = min(m, steps)

   	return (flag, m)

m =  dfs(ais, bis)[1]
print m if m < float('inf') else -1

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from itertools import permutations,combinations

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

# 全探索
INF = 10 ** 5
answer = INF
N = ir()
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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back

int main() {
    int N; cin >> N;
    int A[N], B[N];
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];
    
    int dp[1<<N][N];
    rep(i, 1<<N) rep(j, N) dp[i][j] = 10000;
    dp[0][0] = 0;
    
    rep(S, 1<<N) rep(i, N) {
        int cnt = 0;
        rep(j, N) if ((S>>j)&1) cnt++;
        rep(j, N) {
            if ((S>>j)&1) continue;
            if (S!=0) {
                int now;
                if ((cnt-j)%2==0) now = A[j];
                else now = B[j];
                int prev;
                if ((cnt-1-i)%2==0) prev = A[i];
                else prev = B[i];
                if (prev>now) continue;
            }
            int idx = j;
            for (int k=j+1; k<N; k++) if ((S>>k)&1) idx++;
            dp[S|(1<<j)][j] = min(dp[S|(1<<j)][j], dp[S][i]+idx-cnt);
        }
    }
    
    int ans = 10000;
    rep(i, N) ans = min(ans, dp[(1<<N)-1][i]);
    if (ans==10000) cout << -1 << endl;
    else cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
from collections import deque
N,*L = map(int,open('0').read().split())
A = L[:N]
B = L[N:]
ans = 10**10
for i in range(2**N):
  C = []
  D = []
  for j in range(N):
    if i%2==1:
      if j%2==0:
        C.append((A[j],j))
      else:
        D.append((A[j],j))
    else:
      if j%2==0:
        D.append((B[j],j))
      else:
        C.append((B[j],j))
    i >>= 1
  C.sort()
  D.sort()
  C = deque(C)
  D = deque(D)
  m = 0
  p = -1
  for j in range(N):
    if j%2==0:
      if len(C)==0:
        break
      x,k = C.popleft()
      if x<p:
        break
      p = x
      if k>j:
        m += k-j
    else:
      if len(D)==0:
        break
      x,k = D.popleft()
      if x<p:
        break
      p = x
      if k>j:
        m += k-j
  else:
    ans = min(ans,m)
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL : https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d
解説AC

きもすぎBit全探索および転倒数
    （転倒数に結びついたら強い
    　隣通しを入れ替えてsortの操作数→バブルソートの操作数→転倒数
    　これの徹底）

AC例1: 最初に考え付いたのはこっち
    maskでどのindexが裏返しになっているかを保持。
    その状況下で生成される表面の数の配列を作成し(これをLとする)ソート。
    iを[0,n)で回して各A[i],B[i]に対して
    maskをもとにAかBが使用されているかを見る。
    Lにおけるその数のindexとiの差の偶奇は奇数B偶数ならA。
    defalutdictかなんかで各Lの数字とそのindexの偶奇の数とそのindexを保持
    indexとiの差の偶奇とdictからLの各indexが元どの番号にいたかを保持。
    あとは元の番号の配列の転倒数を求めればそのmaskにおける操作数が出る

AC例2: 解説はこっち
    maskではどのindexがすでに左側で固定化されたかを保持。
    巡回セールスマンのようにどこを決めて最後に決めたindexは何か
    というDPでいける。（は？）
    というのもmaskだけではそのマスク内の順番はわからないからね。
    欲しいのはその固定化された物の最大の値なので最悪なんかうまくできるかも
    すごすぎ
    こっちを実装します
    700点をACしたいね(2020/3/25/ 20:05)

    Reference: https://atcoder.jp/contests/keyence2020/submissions/9567775 By:yutaka1999
"""

#solve
def solve():
    n = II()
    A = LI()
    B = LI()
    bit_length = [0] 
    for i in range(n):
        bit_length += [x + 1 for x in bit_length]
    dp = [(-1,-1)] * (1 << n)
    for i in range(n):
        dp[1 << i] = (0, i)
    for mask in range(1 << n):
        dpm, i = dp[mask]
        c = bit_length[mask]
        w = B[i] if 1 & i == c & 1 else A[i]
        cost = c
        for j in range(n):
            if 1 & (mask >> j):
                cost -= 1
            else:
                v = B[j] if 1 & j != c & 1 else A[j]
                if v >= w:
                    vl = dpm[i] + cost
                    if dp[mask | (1 << j)][0] == -1 or dp[mask | (1 << j)][0] > vl:
                        dp[mask | (1 << j)] = (vl, j)

    print(dp[-1])

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#from collections import *
from itertools import *
#from bisect import *
#from heapq import *
#import copy
#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]
#import math

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
Zlst=set([i for i in range(N)])
count=-1
for lst in combinations(range(N),N//2+N%2):
    odds=[[A[i],i] if i%2==0 else [B[i],i] for i in lst]
    even=[[B[i],i] if i%2==0 else [A[i],i] for i in list(Zlst-set(lst))]
    oddsst=sorted(odds,key=lambda  x:x[0])
    evenst=sorted(even,key=lambda  x:x[0])

    temp=oddsst[0][0]
    lst=[oddsst[0][1]]
    for i in range(1,N):
        if i%2==1:
            ntemp=evenst[i//2]
        else:
            ntemp=oddsst[i//2]
        if temp>ntemp[0]:
            flag=0
            break
        else:
            flag=1
            temp=ntemp[0]
            lst.append(ntemp[1])

    if flag:
        if count==-1:
            count=10**10
        tempcount=0
        while flag:
            flag=0
            for i in range(len(lst)-1):
                if lst[i]>lst[i+1]:
                    lst[i],lst[i+1]=lst[i+1],lst[i]
                    tempcount+=1
                    flag=1
        count=min(count,tempcount)


print(count)

Submission status: Runtime Error

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):
  even = []
  odd = []
  x = 0
  tmp = True
  for j in range(N):
    if ((i>>j) & 1):
      if j%2==1:
        even.append([B[j],j])
      else:
        odd.append([B[j],j])
      
    else:
      if j%2==1:
        odd.append([A[j],j])
      else:
        even.append([A[j],j])
        
  if N%2==0:
    if len(even)!=len(odd):
      continue
      
  else:
    if (len(even)-1)!=len(odd):
      continue
      

  even = sorted(even,key = lambda x:x[0])
  odd = sorted(odd,key = lambda x:x[1])
  ind = [0]*N
  for k in range(N//2):
    o = odd[k]
    e = even[k]
    if (o[0]<e[0])or(o[0]>even[k+1][0]):
      tmp = False
      break
  
    else:
      ind[2*k]=e[1]
      ind[2*k+1]=o[1]
      
  if tmp:
    if N%2==1:
      ind[N-1]=even[-1][1]
    for k in range(N):
      y = ind[k]
      x+=abs(y-k)
      ind = [x+1 if (x<y)and(x>=k) else x for x in ind]
    ans = min(ans,x)
    judge = True
    
if judge:
  print(ans)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
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]]=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()))
import itertools
xx=[i for i in range(n)]
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in itertools.combinations(xx,(n+1)//2):
  s=set(i)
  ac=[]
  bc=[]
  for j in range(n):
    if j in s:ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  m=[]
  for j in range(n):
    if j%2:
      x.append(bc[j//2][0])
      m.append(bc[j//2][1])
    else:
      x.append(ac[j//2][0])
      m.append(ac[j//2][1])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Submission status: Runtime Error

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

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i,0])
        else:
            l.append([B[i],i,1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort()
    d = defaultdict(list)
    for i in range(N):
        v,j,k = l[i]
        if (i-j+k)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000):
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
inf=100000
ans=inf

for i in range(1<<n):#for i in range(2**n)と同じ
    x=[[a[j],j,0] if ((i >> j) & 1) == 1 else [b[j],j,1] for j in range(n)]
    y=[x[j][0] for j in range(n)]
    x.sort()
    for j in range(n):
        if abs(x[j][1]-j)%2!=x[j][2]:
            break
    else:
        c=0
        for j in range(0,n-1):
            for k in range(n-1,j,-1):
                if y[k]<y[k-1]:
                    y[k],y[k-1]=y[k-1],y[k]
                    c+=1
                if c>=ans:
                    break
            if c>=ans:
                break
        else:
            ans=c
if ans==inf:
    print(-1)
else:
    r
    print(ans)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

signed main(){
  int n;cin >> n;
  vector<int> a(n);for(int i=0;i<n;i++) cin >> a[i];
  vector<int> b(n);for(int i=0;i<n;i++) cin >> b[i];
  int inf=10000000;
  int ans=inf;
  for(int i=0;i<(1<<n);i++){
    vector< vector<int> > x(n,vector<int>(3));
    for(int j=0;j<n;j++){
      if(((i>>j)&1)==1){
        x[j][0]=a[j];x[j][1]=j;x[j][2]=0;
      }else{
        x[j][0]=b[j];x[j][1]=j;x[j][2]=1;
      }
    }
    vector<int> y(n);
    for(int j=0;j<n;j++){y[j]=x[j][0];}
    sort(x.begin(),x.end());
    bool f=true;
    for(int j=0;j<n;j++){
      if(abs(x[j][1]-j)%2!=x[j][2]){f=false;break;}
    }
    //for(int j=0;j<n;j++){cout << x[j][0] << " " << x[j][1] << " " << x[j][2] << endl;}
    if(f){
      int c=0;
      for(int j=0;j<n;j++){
        for(int k=j;k>0;k--){
          if(y[k]>=y[k-1])break;
          else{swap(y[k],y[k-1]);c+=1;}
          if(c==ans)break;
        }
        if(c==ans)break;
      }
      //cout << ans <<endl;
      ans=min(ans,c);
    }
  }
  if(ans==inf){
    cout << -1 << endl;
  }else{
    cout << ans << endl;
  }
}