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:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def pop_count(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
cards = [[]] * 2
cards[0] = LIST()
cards[1] = LIST()

# dp[S][i] := 既に使用したカードの集合がSで、最後に使った(現在の右端の)カードがiの時の最小合計転倒数
dp = list2d(1<<N, N, INF)
for i in range(N):
    # 一番左は何が来ても転倒数0
    dp[1<<i][i] = 0
for S in range(1, 1<<N):
    popcnt = pop_count(S)
    # 各位置より元indexが右側にある出現済要素の個数(転倒数)を前計算しておく
    acc = [0] * N
    for i in range(N):
        if S & 1<<i:
            acc[i] = 1
    # 後ろから累積和
    acc = list(accumulate(acc[::-1]))[::-1]
    for i in range(N):
        if dp[S][i] == INF or not S & 1<<i:
            continue
        # 遷移元の右端カードの表裏を確定
        cur = cards[(i&1)^(1-(popcnt&1))][i]
        for j in range(N):
            if S & 1<<j:
                continue
            # 遷移先の右端カードの表裏を確定
            nxt = cards[(j&1)^(popcnt&1)][j]
            # 昇順が崩れないなら遷移させてOK
            if cur <= nxt:
                # 転倒数を追加して遷移
                dp[S|1<<j][j] = min(dp[S|1<<j][j], dp[S][i] + acc[j])
ans = INF
for i in range(N):
    ans = min(ans, dp[(1<<N)-1][i])
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def pop_count(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
cards = [[]] * 2
cards[0] = LIST()
cards[1] = LIST()

# dp[S][i] := 既に使用したカードの集合がSで、最後に使った(現在の右端の)カードがiの時の最小合計転倒数
dp = list2d(1<<N, N, INF)
for i in range(N):
    # 一番左は何が来ても転倒数0
    dp[1<<i][i] = 0
for S in range(1, 1<<N):
    popcnt = pop_count(S)
    # 各位置より元indexが右側にある出現済要素の個数(転倒数)を前計算しておく
    acc = [0] * N
    for i in range(N):
        if S & 1<<i:
            acc[i] = 1
    # 後ろから累積和
    acc = list(accumulate(acc[::-1]))[::-1]
    for i in range(N):
        if dp[S][i] == INF or not S & 1<<i:
            continue
        # 遷移元の右端カードの表裏を確定
        cur = cards[(i%2)^(1-popcnt%2)][i]
        for j in range(N):
            if S & 1<<j:
                continue
            # 遷移先の右端カードの表裏を確定
            nxt = cards[(j%2)^(popcnt%2)][j]
            # 昇順が崩れないなら遷移させてOK
            if cur <= nxt:
                # 転倒数を追加して遷移
                dp[S|1<<j][j] = min(dp[S|1<<j][j], dp[S][i] + acc[j])
ans = INF
for i in range(N):
    ans = min(ans, dp[(1<<N)-1][i])
if ans == INF:
    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()))

ans = N ** 2
for i in range(1 << N):
  L = [[] for _ in range(N)]
  T = [0] * N
  t = i
  for j in range(N):
    if t & 1:
      L[j] = [A[j], 1]
      T[j] = A[j]
    else:
      L[j] = [B[j], 0]
      T[j] = B[j]
    t >>= 1
  D = [0] * N
  T.sort()
  cnt = 0
  for j in range(N):
    c = 0
    for k in range(N):
      if D[k] == 0:
        if L[j][0] == T[k] and (j + 1 - L[j][1]) % 2 == k % 2:
          D[k] = 1
          cnt += j - c
          break
      else:
        c += 1
    else:
      break
  else:
    ans = min(ans, cnt)

if ans == N ** 2:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def pop_count(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
cards = [[]] * 2
cards[0] = LIST()
cards[1] = LIST()

ans = INF
for S in range(1<<N):
    # 無理なケース(奇数枚裏返す)を除外
    if pop_count(S) % 2 != 0:
        continue
    # 奇数位置と偶数位置で分けて保持する
    A1 = [[] for i in range(2)]
    for i in range(N):
        # カードiを青くする
        if S & 1<<i:
            A1[(i%2)^1].append((cards[1][i], i))
        # 赤のまま
        else:
            A1[i%2].append((cards[0][i], i))
    # 無理なケース(置きたい偶奇位置の数がおかしい)を除外
    if len(A1[0]) != ceil(N, 2) or len(A1[1]) != N // 2:
        continue
    # 偶奇が同じ位置同士は自由に動けるのでソートする
    A1[0].sort(reverse=1)
    A1[1].sort(reverse=1)
    cnt = 0
    A2 = [0] * N
    idxs = [0] * N
    for i in range(N):
        # 偶奇位置を交互に取り出す
        A2[i], idxs[i] = A1[i%2].pop()
    # ソート済と一致すればOK
    if A2 == sorted(A2):
        # 移動距離を転倒数数え上げで求める(Nが小さいのでN^2かけて大丈夫)
        cnt = 0
        for i, idx1 in enumerate(idxs):
            for j, idx2 in enumerate(idxs[i+1:], i+1):
                if idx1 > idx2:
                    cnt += 1
        ans = min(ans, cnt)
if ans == INF:
    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()))
INF = N**3
max_ab = max(max(A),max(B))+1
dp = [[INF] * max_ab for _ in range(2**N)]
dp[0][0]=0
for i in range(2**N):
  done = 0
  for j in range(N):
    if (i>>j)&1:
      done += 1
  
  for right_end in range(max_ab):
    if dp[i][right_end]==INF:
      continue
    for add_last in range(N):
      if (i>>add_last)&1:
        continue
      if abs(add_last-done)%2==0:
        add_last_surface = A[add_last]
      else:
        add_last_surface = B[add_last]
        
      if right_end>add_last_surface:
        continue
        
      num = 0
      for k in range(add_last):
        if (i>>k)&1==0:
          num+=1
          
      dp[i|1<<add_last][add_last_surface]=min(dp[i|1<<add_last][add_last_surface],
                                              dp[i][right_end]+num)
      
ans = min(dp[-1])
if ans==INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  # M:カードの数字の最大値+1
  M = max(max(A),max(B))+1
  INF=float('inf')
  # dp[mask][a]:maskのカードが操作済で、そのうち右端のカードの数字がaであるときの操作回数の最小値
  dp = [[INF for _ in range(M)] for _ in range(1<<N)]
  dp[0][0] = 0
  
  for i in range(1<<N):
    # idx:操作済カードの枚数
    idx = 0
    for k in range(N):
      #k番目のカードが操作済みかどうか判定する。iでk番目にフラグがたってたら、操作済みとする。
      if (i>>k)&1 == 1:
        idx += 1
    for j in range(M):
      if dp[i][j] >= INF:
        continue
      for k in range(N):
        # k:右端の操作済カードの次に来るカード
        # kがすでに操作済の場合はcontinueする
        if (i>>k)&1:
          continue
        
        # kが何回操作されるかによってkの数字が表の数字になるか裏の数字になるかが決まる
        if abs(k-idx)%2 == 0:
          c = A[k]
        else:
          c = B[k]
  
        # kの数字広義単調増加にならない場合はcontinue
        if j > c:
          continue
        
        # t:kを右端の操作済カードの次に並べるための操作回数
        # それは、初期配置でkより左にあってまだ操作済でないカードの枚数と一致する
        t = 0
        for l in range(k):
          if (i>>l)&1 == 0:
            t += 1
        #print(i,k,idx,c,dp[i|(1<<k)][c],t)
        dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+t)
  
  ans = INF
  for i in range(M):
    ans = min(dp[(1<<N)-1][i],ans)
  print(ans if ans < INF else -1)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ab=lambda i,j:a[i] if abs(i-j)%2==0 else b[i]
inf=10**9
dp=[n*[inf]for _ in range(1<<n)]
dp[0][0]=0
for i in range(n):dp[1<<i][i]=i
for bit in range(1,1<<n):
  m=[0]*n
  ii=0
  for i in range(n):
    if bit&1<<i:
      m[i]=ii
      ii+=1
  bit_count=ii
  for i in range(n):
    if bit&1<<i==0:
      m[i]=ii
      ii+=1
  for i in range(n):
    if bit&1<<i:continue
    ci=ab(i,bit_count)
    for j in range(n):
      if bit&1<<j==0:continue
      cj=ab(j,bit_count-1)
      if cj>ci:continue
      dp[bit|(1<<i)][i]=min(dp[bit|(1<<i)][i],dp[bit][j]+m[i]-bit_count)
ans=inf
for i in range(n):ans=min(ans,dp[-1][i])
if ans==inf:ans=-1
print(ans)

Submission status: Accepted

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

def count(P):
    res = 0
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(N+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return


    Pi = [None]*N
    for i in range(N):
        Pi[P[i]] = i
    for i in range(N):
        p = Pi[i]
        res += i-BIT_query(p+1)
        BIT_update(p+1, 1)
    return res
 

N = int(input())
A = tuple(map(int,input().split()))
B = tuple(map(int,input().split()))
uhalf = -(-N//2)
dhalf = N - uhalf
inf = 10**9+7
ans = inf
for S in range(1<<N):
    card = [A[i] if S&(1<<i) else B[i] for i in range(N)]
    parity = [(1&(S>>i))^(i&1) for i in range(N)]
    even = [(card[i], i) for i in range(N) if parity[i]]
    odd = [(card[i], i) for i in range(N) if not parity[i]]
    if len(even) != uhalf or len(odd) != dhalf:
        continue
    even.sort()
    odd.sort()
    if any(e[0] > o[0] for e, o in zip(even, odd)) or any(e[0] < o[0] for e, o in zip(even[1:], odd)):
        continue
    perm = [even[i//2][1] if not i&1 else odd[i//2][1] for i in range(N)]
    ans = min(ans, count(perm))
print(ans if ans < inf else -1)

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  # M:カードの数字の最大値+1
  M = max(max(A),max(B))+1
  
  INF = float('inf')
  # dp[mask][a]:maskのカードが操作済で、そのうち右端のカードの数字がaであるときの操作回数の最小値
  dp = [[INF for _ in range(M)] for _ in range(1<<N)]
  dp[0][0] = 0
  
  for i in range(1<<N):
    # idx:操作済カードの枚数
    idx = 0
    for k in range(N):
      if (i>>k)&1 == 1:
        idx += 1
    for j in range(M):
      if dp[i][j] >= INF:
        continue
      for k in range(N):
        # k:右端の操作済カードの次に来るカード
        # kがすでに操作済の場合はcontinueする
        if i&(1<<k) == 1:
          continue
        
        # kが何回操作されるかによってkの数字が表の数字になるか裏の数字になるかが決まる
        if abs(k-idx)%2 == 0:
          c = A[k]
        else:
          c = B[k]
  
        # kの数字広義単調増加にならない場合はcontinue
        if j > c:
          continue
        
        # t:kを右端の操作済カードの次に並べるための操作回数
        # それは、初期配置でkより左にあってまだ操作済でないカードの枚数と一致する
        t = 0
        for l in range(k):
          if (i>>l)&1 == 0:
            t += 1
        #print(i,k,idx,c,dp[i|(1<<k)][c],t)
        dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+t)
  
  #print(dp)
  ans = INF
  for i in range(M):
    ans = min(dp[(1<<N)-1][i],ans)
  print(ans if ans < INF else -1)

if __name__ == '__main__':
  main()

Submission status: Accepted

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[0])
  ind = [0]*N
  for k in range(N//2):
    o = odd[k]
    e = even[k]
    if o[0]<e[0]:
      tmp = False
      break
    
    if (k!=N//2-1)or(N%2==1):
      if o[0]>even[k+1][0]:
        tmp = False
        break
    
    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: Accepted

Solution code:
#bit全探索


#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#Binary Indexed Tree (1-indexなので注意！！！！！！！！)
class BinaryIndexedTree():
    def __init__(self, size):
        self.__node=[0]*(size+1)
        self.size = size

    #node[index]にvalueを足して、BITを更新
    def add(self, index, value):
        while index <= self.size:
            self.__node[index] += value
            index += index&-index    
    
    #indexまでの和を返す
    def sum(self, index):
        ret = 0 #零元・単位元
        while index > 0:
            ret += self.__node[index]
            index -= index&-index    
        return ret

    def update_max(self, index, value):
        while index <= self.size:
            self.__node[index] = max(self.__node[index], value)
            index += index & -index


    #indexまでの最大値を返す
    def query_max(self, index):
        ret = 0
        while index > 0:
            ret = max(ret, self.__node[index])
            index -= index & -index
        return ret
        
        

    #0-indexでの添字を受け取って、1-indexでの添字での値を返す
    def get_node(self, index):
        return self.__node[index]
def Inversion_number(A):
    N=len(A)
    B=sorted(set(A))
    BIT = BinaryIndexedTree(N)
    res = 0
    for i in range(N):
        idx = bisect_left(B,A[i])
        inverse = i - BIT.sum(idx+1)
        res += inverse
        BIT.add(idx+1,1)
    return res

def main():
    N=I()
    A=LI()
    B=LI()
    max_bit = 1<<N


        
    def check(mask): 
        """
        ビットが立ってるところは裏
        裏になるものは元いる位置から奇数移動
        表になるものは元いる位置から偶数移動
        """
        C=[0]*N
        for i in range(N):
            if (mask>>i&1):
                C[i] = B[i]
            else:
                C[i] = A[i]

        C.sort()
        dic = defaultdict(lambda : deque())
        for j,c in enumerate(C):
            dic[c,j&1].append(j)
        
        indexes = [0]*N
        for i in range(N):
            if (mask>>i&1):
                num,is_odd_idx = (B[i],i&1)
                if dic[num,is_odd_idx^1]:
                    idx = dic[num,is_odd_idx^1].popleft()
                else:
                    return inf
            else:
                num,is_odd_idx = A[i],i&1
                if dic[num,is_odd_idx]:
                    idx = dic[num,is_odd_idx].popleft()
                else:
                    return inf
            indexes[i] = idx

        return Inversion_number(indexes)


    ans = inf
    for mask in range(max_bit):
        res = check(mask)
        if res < ans:
            ans = res
    if ans == inf:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def tentousu(a):
  ans=0
  for i in range(len(a)):
    for j in range(i+1,len(a)):
      if a[i]>a[j]:ans+=1
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Submission status: Accepted

Solution code:
def tentousu(a):
  ans=0
  for i in range(len(a)):
    for j in range(i+1,len(a)):
      if a[i]>a[j]:ans+=1
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  if s.count("1")!=n//2 and s.count("1")!=n//2+1:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Submission status: Accepted

Solution code:
def tentousu(a):
  ans=0
  for i in range(len(a)):
    for j in range(i+1,len(a)):
      if a[i]>a[j]:ans+=1
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from operator import itemgetter
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:]
    if n.count('1')%2!=0:
        continue
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i])
        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(key=itemgetter(0))
    d = defaultdict(list)
    for i in range(N):
        v,j = l[i]
        if (i-j)%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: Accepted

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 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 f(bit)%2!=0:
    #     continue
    arr=[]
    for i in range(n):
        if bit >> i & 1:
            arr.append((B[i],i))
        else:
            arr.append((A[i],i))
    i=0;flug=1;tmp=0
    while flug:
        flug=0
        for j in range(n-1,i,-1):
            if arr[j-1][0]>arr[j][0]:
                arr[j-1],arr[j]=arr[j],arr[j-1]
                tmp+=1; flug=1
        i+=1
    stack=[]
    for i in range(n):
        if (abs(arr[i][1]-i)) % 2 != bit >> arr[i][1] & 1:
            stack.append(arr[i][0]*1000+i)
    # if bit == 3:
        # print(tmp,stack,arr,bin(bit))
        # print((abs(arr[1][1]-1)) % 2 , bit >> arr[1][1])
    if len(stack) & 1:
        tmp=1000; stack.pop()
    while stack:
        p=stack.pop(); q=stack.pop()
        if (p-q) & 1:
            tmp+=p-q
            # if bit==3:
                # print(p,q,tmp,mans)
                # print(arr)
        else:
            tmp+=1000
    mans=min(mans,tmp)

print(-1 if mans > 999 else mans)

Submission status: Accepted

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]

ans = 1 << 100
for m in range(1<<N):
    b = bin(m)
    if b[::2].count("1") != b[1::2].count("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]) << 5) + i)
    if len(C[1]) != N // 2: continue
    C[0].sort()
    C[1].sort()
    CC = [C[i&1][i//2] for i in range(N)]
    for i in range(1, N):
        if CC[i-1] >> 5 > CC[i] >> 5: break
    else:
        CCC = [c % 32 for c in CC]
        t = 0
        for i in range(N):
            for j in range(i):
                if CCC[i] < CCC[j]: t += 1
        ans = min(ans, t)
print(ans if ans < 1 << 100 else -1)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AB = sorted(list(set(A + B)))
D = {ab: i+1 for i, ab in enumerate(AB)}
A = [D[a] for a in A]
B = [D[a] for a in B]

def chk(L):
    NN = 5
    BIT=[0] * (2**NN+1)
    def addbit(i):
        while i <= 2**NN:
            BIT[i] += 1
            i += i & (-i)
 
    def getsum(i):
        ret = 0
        while i != 0:
            ret += BIT[i]
            i -= i&(-i)
        return ret
    s = 0
    for l in L[::-1]:
        s += getsum(l+1)
        addbit(l+1)
    return s
ans = 1 << 100
for m in range(1<<N):
    b = bin(m)
    if b[::2].count("1") != b[1::2].count("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]) << 5) + i)
    if len(C[1]) != N // 2: continue
    C[0].sort()
    C[1].sort()
    CC = [C[i&1][i//2] for i in range(N)]
    for i in range(1, N):
        if CC[i-1] >> 5 > CC[i] >> 5: break
    else:
        CCC = [c % 32 for c in CC]
        ans = min(ans, chk(CCC))
print(ans if ans < 1 << 100 else -1)

Submission status: Accepted

Solution code:
from itertools import combinations

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

def Inversion(seq):
    seq = [i + 1 for i in seq]
    # seqは、1,2,...,Nの順列 (0-indexだったので合わせた。)
    N = len(seq)
    bit = BinaryIndexedTree([0] * (N+1))
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

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

# 偶数/奇数の位置に来るindex達を生成する。Combinations(range(N), N//2)
# 偶数だけの列と奇数だけの列を作って、それぞれソート。(転倒数を計算したいので、valとともにindex番号も持っておく)
# 数字と位置の偶奇が異なる場合はB面、一致しているときはA面を使う。
# 上記の２つの数列を一つにまとめた時に広義単調増加になっているかを判定。
# 最小の移動回数が答え。存在しない場合は-1
# 最小の操作回数⇒転倒数

# combinations(n, n//2)が偶数の位置に来るindex。
ptn = list(combinations(range(N), N//2))

ans = - 1
for p in ptn:
  evnline = []
  oddline = []
  for i in range(N):
    if i in p:
      evnline.append((A[i] if (i + 1) % 2 == 0 else B[i], i))
    else:
      oddline.append((B[i] if (i + 1) % 2 == 0 else A[i], i))
  line = [0] * N
  evnline.sort()
  oddline.sort()
#   print("e, o", evnline, oddline)
  for itr, val in enumerate(evnline):
    line[itr * 2 + 1] = val
  for itr, val in enumerate(oddline):
    line[itr * 2] = val
  if all([j[0] >= i[0] for i, j in zip(line,line[1:])]):
    exchange_cnt = Inversion([i[1] for i in line])
    if ans == -1:
      ans = exchange_cnt
    else:
      ans = min(ans, exchange_cnt)

print(ans)

Submission status: Accepted

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

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

for bit in range(1 << N):
    # 左詰めソートされている数
    con = bin(bit).count("1")

    # bitに含まれないカード
    ords = []
    iters = con
    for i in range(N):
        if not (bit & (1 << i)):
            ords.append([i, iters])
            iters += 1

    for s in range(51):
        if dp[bit][s] >= INF:
            continue

        for p in ords:
            # p[0]: 元々のindex, p[1]: dp[bit][s]の状態でのindex
            # con: bitの中身の数（既に詰まっているindexの最後尾）
            # |i-j|が偶数ならばA[i], 奇数ならばB[i]
            ns = A[p[0]] if abs(p[0] - con) % 2 == 0 else B[p[0]]

            # bitの中身がcon枚なので，bitに含まれないものはcon+1から順に詰める
            # 新しく詰める値nsが，既に詰まっている値の最大値sよりも大きい場合，
            # その値を後ろに詰める．
            if ns >= s:
                # 詰める時の最小の操作回数をdpで調べる．
                dp[bit|(1 << p[0])][ns] = min(dp[bit|(1 << p[0])][ns],
                                              dp[bit][s] + abs(con - p[1]))

ans = min(dp[-1][s] for s in range(51))
print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
import sys
import itertools
INF = float("INF")

N = int(input())
AA = list(map(int, sys.stdin.readline().split()))
BB = list(map(int, sys.stdin.readline().split()))

cards = set()
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.add((a, b, i))
    else:
        cards.add((b, a, i))

def solve(ii):
    tmp = 0
    for i in range(N):
        for j in range(i+1,N):
            if ii[i] > ii[j]:
                tmp += 1
    return tmp

ans = INF
for Acards in itertools.combinations(cards, (N+1)//2):
    Bcards = cards - set(Acards)

    Ais = sorted([(card[0], card[2]) for card in Acards])
    Bis = sorted([(card[1], card[2]) for card in Bcards])

    bn = -1
    ii = []
    flag = False
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        if bn > n: # 組み合わせた時広義単調増加になってない
            flag = True
            break
        bn = n
        ii.append(i)

    if flag: continue

    ans = min(ans,solve(ii))


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