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:
from itertools import combinations

def solve():
    INF = 10**5

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    ans = INF
    for iEvens in combinations(range(N), r=N//2):
        iEvens = set(iEvens)
        COdds, CEvens = [], []
        for i in range(N):
            if i in iEvens:
                if i % 2:
                    CEvens.append((As[i], i))
                else:
                    CEvens.append((Bs[i], i))
            else:
                if i % 2:
                    COdds.append((Bs[i], i))
                else:
                    COdds.append((As[i], i))
        COdds.sort()
        CEvens.sort()

        Cs = []
        for COdd, CEven in zip(COdds, CEvens):
            Cs += [COdd[0], CEven[0]]
        if N % 2:
            Cs += [COdds[-1][0]]

        for i in range(N-1):
            if Cs[i] > Cs[i+1]:
                break
        else:
            num = 0
            p = 0
            for COdd, i in COdds:
                num += abs(p-i)
                p += 2
            p = 1
            for CEven, i in CEvens:
                num += abs(p-i)
                p += 2
            num //= 2
            ans = min(ans, num)

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


solve()

Submission status: Wrong Answer

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

M = max(max(A),max(B))+1

INF = float('inf')
dp = [[INF for _ in range(M)] for _ in range(1<<N)]
dp[0][0] = 0

for i in range(1<<N):
  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):
      if i&(1<<k) == 1:
        continue
      if abs(k-idx)%2 == 0:
        c = A[k]
      else:
        c = B[k]
      if j > c:
        continue
      #print(i,k,idx,c,dp[i|(1<<k)][c],max(k-idx,0))
      dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+max(k-idx,0))

#print(dp)
ans = INF
for i in range(M):
  ans = min(dp[(1<<N)-1][i],ans)
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()))
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]:
      tmp = False
      break
    
    elif k!=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: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
judge = False
ans = 10**9
for i in range(2**N):
  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]:
      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: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res


n = I()
A = LI()
B = LI()
ans = INF
for even_iter in combinations(range(n), (n + 1) // 2):
    even_set = set(even_iter)
    odd = []
    even = []
    s = []
    # Aの配列をswapした結果、evenの枠にはこのsetがくるとする。
    for i in range(n):
        if i in even_set:
            even += [(B[i], i) if i % 2 else (A[i], i)]
            s += [B[i] if i % 2 else A[i]]
        else:
            odd += [(A[i], i) if i % 2 else (B[i], i)]
            s += [A[i] if i % 2 else B[i]]

    even.sort(reverse=True)
    odd.sort(reverse=True)
    t = []
    while even:
        t += [even.pop()]
        if odd:
            t += [odd.pop()]
    if sorted(t) != t:
        continue
    bit = BIT(51)
    cost = 0
    for k in range(n - 1, -1, -1):
        cost += bit.sum(s[k] - 1)
        bit.add(s[k], 1)
    ans = min(ans, cost)


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

Submission status: Wrong Answer

Solution code:
# https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361#8-next_combination
# http://drken1215.hatenablog.com/entry/2020/01/19/025500

def enumerate_next_combinations(n: int, k: int) -> list:
    """要素数がn個の集合{0,...,N-1}の要素数がk個の部分集合を全列挙
    :return [{要素数がk個の部分集合},{},...]
    """

    def _next_combination(sub):
        x = sub & -sub  # subの最下位の1のbit
        y = sub + x  # subの最下位の1の連続している区間の1つ上の0のbitを1にして、それ以下のbitを0にする
        return (((sub & ~y) // x) >> 1) | y
        # sub & ~y: subの最下位の1の連続している区間
        # //x: subの最下位の1の連続している区間の右側の0を（右シフトで）なくしたもの
        # >>1: subの最下位の1の連続している区間の右側の0を（右シフトで）なくしたもののbitの数を1減らしたもの

    ret = []
    if k == 0:
        return ret

    bit = (1 << k) - 1
    while bit < (1 << n):
        st = {j for j in range(n) if bit & (1 << j)}
        ret.append(st)
        bit = _next_combination(bit)

    return ret


def main():
    from collections import namedtuple

    inf = 1 << 29

    Card = namedtuple('Card', 'i_ a_ b_')  # 0-indexed
    Card.front = lambda self, i: self.a_ if (self.i_ - i) % 2 == 0 else self.b_  # 0-indexedでiに移動したときの表面の数値
    #  WA, if (self.i_ - i) % 2 == 0 <- ==0つけ忘れていた

    def sum_of_powers(set_: set) -> int:
        """set_->2の冪の総和"""
        return sum(1 << j for j in set_)

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

    cards = [Card(i_=i_, a_=a_, b_=b_) for i_, (a_, b_) in enumerate(zip(a, b))]

    dp = [[inf] * (50 + 1) for _ in range(1 << n)]
    dp[0][0] = 0
    # dp[bit][末尾の番号]=カードの移動距離の総和の最小値
    for k in range(1, n + 1):
        for set_ in enumerate_next_combinations(n, k):
            # set_: 要素数がk個の集合
            # 左端からset_のカードを昇順に並べる
            bit = sum_of_powers(set_)  # {0,1,3} -> 1+2+8=11
            for tail_cand in set_:  # set_を昇順に並べたときの末尾のカードの候補
                front_ = cards[tail_cand].front(k - 1)  # 候補のカードを位置kまで移動したときの表面の数値 <- WA, k-1忘れていた
                for prev in range(50 + 1):
                    if dp[bit & ~(1 << tail_cand)][prev] < inf and prev <= front_:
                        dp[bit][front_] = min(
                            dp[bit][front_],
                            dp[bit & ~(1 << tail_cand)][prev] + abs(k - 1 - tail_cand)
                        )

    tot = min(dp[(1 << n) - 1])
    if tot == inf:
        print(-1)
        return
    tot //= 2
    print(tot)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361#8-next_combination
# http://drken1215.hatenablog.com/entry/2020/01/19/025500

def enumerate_next_combinations(n: int, k: int) -> list:
    """要素数がn個の集合{0,...,N-1}の要素数がk個の部分集合を全列挙
    :return [{要素数がk個の部分集合},{},...]
    """

    def _next_combination(sub):
        x = sub & -sub  # subの最下位の1のbit
        y = sub + x  # subの最下位の1の連続している区間の1つ上の0のbitを1にして、それ以下のbitを0にする
        return (((sub & ~y) // x) >> 1) | y
        # sub & ~y: subの最下位の1の連続している区間
        # //x: subの最下位の1の連続している区間の右側の0を（右シフトで）なくしたもの
        # >>1: subの最下位の1の連続している区間の右側の0を（右シフトで）なくしたもののbitの数を1減らしたもの

    ret = []
    if k == 0:
        return ret

    bit = (1 << k) - 1
    while bit < (1 << n):
        st = {j for j in range(n) if bit & (1 << j)}
        ret.append(st)
        bit = _next_combination(bit)

    return ret


def main():
    from collections import namedtuple

    inf = 1 << 29

    Card = namedtuple('Card', 'i_ a_ b_')  # 0-indexed
    Card.front = lambda self, i: self.a_ if (self.i_ - i) % 2 else self.b_  # 0-indexedでiに移動したときの表面の数値

    def sum_of_powers(set_: set) -> int:
        """set_->2の冪の総和"""
        return sum(1 << j for j in set_)

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

    cards = [Card(i_=i_, a_=a_, b_=b_) for i_, (a_, b_) in enumerate(zip(a, b))]

    dp = [[inf] * (50 + 1) for _ in range(1 << n)]
    dp[0][0] = 0
    # dp[bit][末尾の番号]=カードの移動距離の総和の最小値
    for k in range(n + 1):
        for set_ in enumerate_next_combinations(n, k):
            # set_: 要素数がk個の集合
            # 左端からset_のカードを昇順に並べる
            bit = sum_of_powers(set_)  # {0,1,3} -> 1+2+8=11
            for tail_cand in set_:  # set_を昇順に並べたときの末尾のカードの候補
                front_ = cards[tail_cand].front(k)  # 候補のカードを位置kまで移動したときの表面の数値
                for prev in range(50 + 1):
                    if dp[bit & ~(1 << tail_cand)][prev] >= 0 and prev <= front_:
                        dp[bit][front_] = min(
                            dp[bit][front_],
                            dp[bit & ~(1 << tail_cand)][prev] + abs(k - 1 - tail_cand)
                        )

    tot = min(dp[(1 << n) - 1])
    if tot == inf:
        print(-1)
        return
    tot //= 2
    print(tot)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
odd = []
even = []

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

for i in range(n,n*2):
    for j in range(n):
        if  j != i % n and odd[i % n] <= even[j]:
            graph[i].append(j)
#グラフで一筆書きをする。パスがnになったら終わり。その順番を実現するために考える
def clear_maze(start):
    que = deque()
    que.append([start, set([start]), [start]])
    while que:
        node, f, p = que.popleft()
        if len(p) == n:
            check(p)
        else:
            for i in graph[node]:
                if i % n not in f:
                    que.append([i, f|set([i%n]), p + [i]])

def check(path):
    #この順番に並ぶための最小
    #print(path)
    array = [i % n for i in path]
    cand = 0
    global ans
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if array[j] < array[j-1]:
                cand += 1
    ans = min(cand, ans)
inf = 18**2
ans = inf
for i in range(n):
    #iから始める迷路を解く
    clear_maze(i)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
ans = 10**9


def count_inversion(sequence):
    return sum(sum(m < n for m in sequence[i+1:]) for i, n in enumerate(sequence))


for i in range(2**N):
    tmp = [0]*N
    count = 0
    for j in range(N):
        if (i >> j) % 2 == 1:
            tmp[j] = (A[j], j)

        else:
            tmp[j] = (B[j], j)
            count += 1
    if count % 2 == 1:
        continue
    tmp.sort()
    flag = True
    tmp2 = [0]*N
    for j in range(N):
        if abs(tmp[j][1] - j) % 2 == 0:
            if tmp[j][0] != A[tmp[j][1]]:
                flag = False
                break
        else:
            if tmp[j][0] != B[tmp[j][1]]:
                flag = False
                break
    if flag:
        tmp.sort(key=lambda x: x[1])
        tmp2 = [tmp[i][0] for i in range(N)]
        tmp_ans = count_inversion(tmp2)
        ans = min(tmp_ans, ans)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
odd = []
even = []

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

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
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)]
    #org=[A[i] if not((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)]
    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
    
    i=0
    flag=True
    while i<N:
      if cnt[i]%2==1:
        if i==N-1:
          flag=False
          break
        else:
          if C[i+1]==C[i] and cnt[i+1]%2==1:
            cnt[i]+=1
            cnt[i+1]+=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:
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)]
    #org=[A[i] if not((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)]
    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
    
    i=0
    flag=True
    while i<N:
      if cnt[i]%2==1:
        if i==N-1:
          flag=False
          break
        else:
          if C[i+1]==C[i] and cnt[i+1]%2==1:
            cnt[i]+=1
            cnt[i+1]+=1
            i+=1
            ans+=1
          else:
            flag=False
            break
      i+=1
    if flag:
      Ans=min(ans,Ans)
    return
  if Ans==N**2+1:
    print(-1)
  else:
    print(Ans)
  return
          
main()

Submission status: Wrong Answer

Solution code:
# from collections import defaultdict,deque
# import sys,heapq,bisect,math,itertools,string,queue,copy,time
# sys.setrecursionlimit(10**8)
#
#
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
        bn = n
        ii.append(i)

    if flag: continue

    ans = min(ans,solve(ii))

    if ans == 0:
        print(0)


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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
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(1,n):
            for k in range(j,0,-1):
                if y[k] >= y[k-1]:
                    break
                else:
                    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:
    print(ans)

Submission status: Wrong Answer

Solution code:
# from collections import defaultdict,deque
# import sys,heapq,bisect,math,itertools,string,queue,copy,time
# sys.setrecursionlimit(10**8)
#
#
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 _ in range(N):
        next = []
        for k, i in enumerate(ii):
            if i == 0:
                tmp += k
            else:
                next.append(i-1)
        ii = next[:]
    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
        ii.append(i)

    if flag:
        continue

    ans = min(ans,solve(ii))


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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
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[i][0] for i in range(n)]
    x.sort()
    for i in range(n):
        if abs(x[i][1]-i)%2!=x[i][2]:
            break
    else:
        c=0
        for i in range(1,n):
            for j in range(i,0,-1):
                if y[j] >= y[j-1]:
                    break
                else:
                    y[j],y[j-1]=y[j-1],y[j]
                    c+=1
                if c>=ans:
                    break
            if c>=ans:
                break
        else:
            ans=c
if ans==inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
inf=100000000000
ans=inf
def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1=0
        i2=0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt
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[i][0] for i in range(n)]
    x.sort()
    for i in range(n):
        if abs(x[i][1]-i)%2!=x[i][2]:
            break
    else:
        c=mergecount(y)
        ans=min(ans,c)
if ans==inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
inf=100000000000
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[i][0] for i in range(n)]
    x.sort()
    for i in range(n):
        if abs(x[i][1]-i)%2!=x[i][2]:
            break
    else:
        c=0
        for i in range(1,n):
            for j in range(i,0,-1):
                if y[j] >= y[j-1]:
                    break
                else:
                    y[j],y[j-1]=y[j-1],y[j]
                    c+=1
        ans=min(ans,c)
if ans==inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
inf=100000000000
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)]
    x.sort()
    y=[x[i][1] for i in range(n)]
    for i in range(n):
        if abs(x[i][1]-i)%2!=x[i][2]:
            break
    else:
        c=0
        for i in range(1,n):
            for j in range(i,0,-1):
                if y[j] >= y[j-1]:
                    break
                else:
                    y[j],y[j-1]=y[j-1],y[j]
                    c+=1
        ans=min(ans,c)
if ans==inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
odd = []
even = []

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
odd = []
even = []

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
odd = []
even = []

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

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