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
n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

even = []   #偶数番目で表になる
odd = []    #奇数番目で表になる
for i,(a,b) in enumerate(zip(As,Bs)):
    if i%2 == 0:
        even.append(a)
        odd.append(b)
    else:
        even.append(b)
        odd.append(a)

def check(n, even, odd):
    xs = even + odd
    xs.sort()
    ps = [0] * n #何番目？というやつ
    # ちゃんと交代交代になっているか
    for i,x in enumerate(xs):
        if i%2 == 0:
            if even[i//2] != x:
                return False, -1
            else:
                ps[i] = even[i//2][1] #その時の順番を保持
        elif i%2 == 1:
            if odd[i//2] != x:
                return False, -1
            else:
                ps[i] = odd[i//2][1]
    return True, ps

def inversion(a):
    n = len(a)
    cnt = 0
    for i in range(n):
        for j in range(i+1,n):
            if a[i] > a[j]:
                cnt +=1
    return cnt     
                
 
 
#偶数としてpickupするやつ
INF = 10**10
ans = 10**10
for l in combinations(range(n), (n-1)//2+1):
    cnt = 0
    even_selected = [(even[i],i) for i in range(n) if i in l]
    odd_selected = [(odd[i],i) for i in range(n) if i not in l]
    # こいつらを昇順に並べられるか
    even_selected.sort()
    odd_selected.sort()
    is_possible, a = check(n,even_selected, odd_selected)
    # 
    if is_possible:
        cnt = inversion(a)
        ans = min(cnt,ans)

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

ans=float("inf")

def dfs(num,r,b):
    global ans
    if num==N:
        eb=0
        ob=0
        for i in b:
            if i%2==0:
                eb+=1
            else:
                ob+=1
        if eb==ob:
            list=[[A[i],i,"r"] for i in range(N)]
            for i in range(N):
                if i in b:
                    list[i][0]=B[i]
                    list[i][2]="b"
            list.sort()
            flag=True
            for i in range(N):
                val,pv,c=list[i]
                if abs(pv-i)%2==0 and c=="b":
                    flag=False
                if abs(pv-i)%2==1 and c=="r":
                    flag=False
            if flag:
                list.sort(key=lambda x:x[1])
                test=0
                for i in range(1,N):
                    for j in range(0,i):
                        if list[j][0]>list[i][0]:
                            test+=1
                ans=min(test,ans)
        return 0

    dfs(num+1,r+[num],b)
    dfs(num+1,r,b+[num])

dfs(0,[],[])
print(ans if ans!=float("inf") else -1)

Submission status: Wrong Answer

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 = []
  C.sort()
  D.sort()
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

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()
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
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(reverse=True)
  D.sort(reverse=True)
  m = 0
  p = -1
  for j in range(N):
    if j%2==0:
      if C==[]:
        break
      x,k = C.pop()
      if x<p:
        break
      p = x
      if k>j:
        m += k-j
    else:
      if D==[]:
        break
      x,k = D.pop()
      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: Wrong Answer

Solution code:
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(reverse=True)
  D.sort(reverse=True)
  ls = []
  p = -1
  for j in range(N):
    if j%2==0:
      if C==[]:
        break
      x,k = C.pop()
      if x<p:
        break
      p = x
      ls.append(k)
    else:
      if D==[]:
        break
      x,k = D.pop()
      if x<p:
        break
      p = x
      ls.append(k)
  else:
    m = sum(k-i if k>i else 0 for i,k in enumerate(ls))
    ans = min(ans,m)
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
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(reverse=True)
  D.sort(reverse=True)
  ls = []
  p = -1
  for j in range(N):
    if j%2==0:
      if C==[]:
        break
      x,k = C.pop()
      if x<p:
        break
      p = x
      ls.append(k)
    else:
      if D==[]:
        break
      x,k = D.pop()
      if x<p:
        break
      p = x
      ls.append(k)
  else:
    m = sum(k-i if k>i else 0 for i,k in enumerate(ls))
    ans = min(ans,m)
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
N,*L = map(int,open(0).read().split())
A = L[:N]
B = L[N:]
ans = 10**10
for i in range(2**N):
  C = []
  for j in range(N):
    if i%2==1:
      C.append((A[j],j,0))
    else:
      C.append((B[j],j,1))
    i >>= 1
  cnt = 0
  C.sort()
  ls = []
  used = [True]*N
  p = -1
  flag = False
  for cnt in range(N):
    for j in range(N):
      if used[j]:
        if p>C[j][0]:
          flag = True
          break
        if C[j][2]==(abs(C[j][1]-cnt))%2:
          used[j] = False
          ls.append(C[j][1])
          p = C[j][0]
          break
    else:
      break
    if flag:
      break
  else:
    m = sum(k-i if k>i else 0 for i,k in enumerate(ls))
    ans = min(ans,m)
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

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 + 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: Wrong Answer

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] * n for _ in range(1 << n)]
    for i in range(n):
        dp[1 << i][i] = 0
    for mask in range(1 << n):
        dpm = dp[mask]
        c = bit_length[mask]
        for i in range(n):
            if not((1 << i) & mask) or dpm[i] == -1: continue
            w = B[i] if 1 & i == c & 1 else A[i]
            cost = c
            for j in range(n):
                cost -= 1 & (mask >> j)
                v = B[j] if 1 & j != c & 1 else A[j]
                if v >= w:
                    vl = dpm[i] + cost
                    if dp[mask | (1 << j)][j] == -1 or dp[mask | (1 << j)][j] > vl:
                        dp[mask | (1 << j)][j] = vl

    ans = -1
    for i in range(n):
        if dp[-1][i] != -1:
            if ans == -1 or ans > dp[-1][i]:
                ans = dp[-1][i]
    print(ans)

    return


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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(2)]
def get_status(p):
    return format(p, 'b').zfill(n-1)
ans=200
for i in range(2**(n-1)):
    s=get_status(i)
    flag=0
    nmb=[h for h in range(n)]
    reversecount=[0]*n
    for j in range(n-1):
        if s[j]=="0":
            continue
        else:
            nmb[j],nmb[j+1]=nmb[j+1],nmb[j]
            reversecount[nmb[j]]+=1;reversecount[nmb[j+1]]+=1
    for j in range(n-1):
        if a[reversecount[nmb[j]]%2][nmb[j]]>a[reversecount[nmb[j+1]]%2][nmb[j+1]]:flag=1;break
    #print(nmb,reversecount)
    if flag:continue
    if s.count("1")<ans:
        ans=s.count("1")
if ans==200:print(-1)
else:print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(2)]
def get_status(p):
    return format(p, 'b').zfill(n-1)
ans=200
for i in range(2**(n-1)):
    s=get_status(i)
    flag=0
    nmb=[h for h in range(n)]
    reversecount=[0]*n
    for j in range(n-1):
        if s[j]=="0":
            continue
        else:
            nmb[j],nmb[j+1]=nmb[j+1],nmb[j]
            reversecount[nmb[j]]+=1;reversecount[nmb[j+1]]+=1
    for j in range(n-1):
        if a[reversecount[j]%2][nmb[j]]>a[reversecount[j+1]%2][nmb[j+1]]:flag=1;break
    if flag:continue
    if s.count("1")<ans:
        ans=s.count("1")
if ans==200:print(-1)
else:print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(2)]
def get_status(p):
    return format(p, 'b').zfill(n-1)
ans=200
for i in range(2**(n-1)):
    s=get_status(i)
    flag=0
    retsu=[[a[0][i],0] for i in range(n)]
    for j in range(n-1):
        if s[j]=="0":
            continue
        else:
            retsu[j]=[a[retsu[j+1][1]^1][j+1],retsu[j+1][1]^1]
            retsu[j+1]=[a[retsu[j][1]^1][j],retsu[j][1]^1]
    for j in range(n-1):
        if retsu[j]>retsu[j+1]:flag=1;break
    if flag:continue
    if s.count("1")<ans:
        ans=s.count("1")
if ans==200:print(-1)
else:print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(2)]
def get_status(p):
    return format(p, 'b').zfill(n)
ans=200
for i in range(2**(n-1)):
    s=get_status(i)
    flag=0
    retsu=[[a[0][i],0] for i in range(n)]
    for j in range(n-1):
        if s[j]=="0":
            continue
        else:
            retsu[j]=[a[retsu[j+1][1]^1][j+1],retsu[j+1][1]^1]
            retsu[j+1]=[a[retsu[j][1]^1][j],retsu[j][1]^1]
    for j in range(n-1):
        if retsu[j]>retsu[j+1]:flag=1;break
    if flag:continue
    if s.count("1")<ans:
        ans=s.count("1")
if ans==200:print(-1)
else:print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(2)]
def get_status(p):
    return format(p, 'b').zfill(n)
ans=200
for i in range(2**(n-1)):
    s=get_status(i)
    flag=0
    retsu=[[a[0][i],0] for i in range(n)]
    for j in range(n-1):
        if s[j]=="0":
            continue
        else:
            retsu[j]=[a[retsu[j+1][1]^1][j+1],retsu[j+1][1]^1]
            retsu[j+1]=[a[retsu[j][1]^1][j],retsu[j][1]^1]
    for j in range(n-1):
        if retsu[j]>retsu[j+1]:flag=1;break
    if flag:continue
    if s.count("1")<ans:
        ans=s.count("1")
if ans==200:print(-1)
else:print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(i):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append(b[j])
    else:
      x.append(a[j])
  sx = sorted(x)
  odd = [0] * 51
  even = [0] * 51
  for j in range(N):
    odd[sx[j]] += j % 2
    even[sx[j]] += (j % 2 == 0)
  for j in range(N):
    if i & (1 << j):
      if j % 2: even[x[j]] -= 1
      else: odd[x[j]] -= 1
    else:
      if j % 2: odd[x[j]] -= 1
      else: even[x[j]] -= 1
  return min(min(odd), min(even)) >= 0
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
res = float("inf")
for i in range(pow(2, N)):
  if check(i) == False: continue
  fwk = BIT(51)
  t = 0
  for j in range(N):
    if i & (1 << j):
      t += fwk.get(b[j] + 1, 51)
      fwk.add(b[j], 1)
    else:
      t += fwk.get(a[j] + 1, 51)
      fwk.add(a[j], 1)
    #print(t, i)
  res = min(res, t)
  #print(res, i)
if res == float("inf"): print(-1)
else: print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(i):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append(b[j])
    else:
      x.append(a[j])
  sx = sorted(x)
  odd = [0] * 51
  even = [0] * 51
  for j in range(N):
    odd[sx[j]] += j % 2
    even[sx[j]] += (j % 2 == 0)
  for j in range(N):
    if i & (1 << j):
      if j % 2: even[x[j]] -= 1
      else: odd[x[j]] -= 1
    else:
      if j % 2: odd[x[j]] -= 1
      else: even[x[j]] -= 1
  return min(min(odd), min(even)) >= 0
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
res = float("inf")
for i in range(pow(2, N)):
  if check(i) == False: continue
  fwk = BIT(51)
  t = 0
  for j in range(N - 1, -1, -1):
    if i & (1 << j):
      t += fwk.sum(b[j] - 1)
      fwk.add(b[j], 1)
    else:
      t += fwk.sum(a[j] - 1)
      fwk.add(a[j], 1)
    #print(t, i)
  res = min(res, t)
  #print(res, i)
if res == float("inf"): print(-1)
else: print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(i):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  x.sort(key = lambda x: x[0])
  for j in range(N):
    if i & (1 << x[j][1]):
      if (j - x[j][1]) % 2 == 0:
        return False
    else:
      if (j - x[j][1]) % 2:
        return False
  return True
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
res = float("inf")
for i in range(pow(2, N)):
  if check(i) == False: continue
  fwk = BIT(51)
  t = 0
  for j in range(N - 1, -1, -1):
    if i & (1 << j):
      t += fwk.sum(b[j])
      fwk.add(b[j], 1)
    else:
      t += fwk.sum(a[j])
      fwk.add(a[j], 1)
    #print(t, i)
  res = min(res, t)
  #print(res, i)
if res == float("inf"): print(-1)
else: print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(i):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  x.sort(key = lambda x: x[0])
  for j in range(N):
    if i & (1 << x[j][1]):
      if (j - x[j][1]) % 2 == 0:
        return False
    else:
      if (j - x[j][1]) % 2:
        return False
  return True
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
res = float("inf")
for i in range(pow(2, N)):
  if check(i) == False: continue
  fwk = BIT(51)
  t = 0
  for j in range(N):
    if i & (1 << j):
      t += fwk.get(b[j] + 1, 51)
      fwk.add(b[j], 1)
    else:
      t += fwk.get(a[j] + 1, 51)
      fwk.add(a[j], 1)
    #print(t, i)
  res = min(res, t)
  #print(res, i)
if res == float("inf"): print(-1)
else: print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(i):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  x.sort(key = lambda x: x[0])
  for j in range(N):
    if i & (1 << x[j][1]):
      if (j - x[j][1]) % 2 == 0:
        return False
    else:
      if (j - x[j][1]) % 2:
        return False
  return True
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
res = float("inf")
for i in range(pow(2, N)):
  if check(i) == False: continue
  fwk = BIT(51)
  t = 0
  for j in range(N):
    if i & (1 << j):
      t += fwk.get(b[j], 51)
      fwk.add(b[j], 1)
    else:
      t += fwk.get(a[j], 51)
      fwk.add(a[j], 1)
    #print(t, i)
  res = min(res, t)
  #print(res, i)
if res == float("inf"): print(-1)
else: print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
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 = 1000000007


n = I()
A = LI()
B = LI()
ans = INF
for odd_ind in combinations(range(n), n // 2):
    even_ind = set(range(n)) - set(odd_ind)
    odd_list = []
    even_list = []
    whole_list = []
    for i in odd_ind:
        if i % 2:
            odd_list += [(A[i], i)]
        else:
            odd_list += [(B[i], i)]
    for j in even_ind:
        if j % 2:
            even_list += [(B[j], j)]
        else:
            even_list += [(A[j], j)]
    even_list.sort(reverse=1)
    odd_list.sort(reverse=1)
    while even_list or odd_list:
        whole_list += [even_list.pop()]
        if odd_list:
            whole_list += [odd_list.pop()]
    if whole_list == sorted(whole_list):
        cnt = 0
        for i in range(n):
            for j in range(i + 1, n):
                if whole_list[i][1] > whole_list[j][1]:
                    cnt += 1
        ans = min(ans, cnt)


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 = float('inf')
ans = INF
for k in range(1<<N):
    arr = []
    for i,(a,b) in enumerate(zip(A,B)):
        if k&(1<<i):
            arr.append((a,i,0))
        else:
            arr.append((b,i,1))
    arr.sort()
    for i,(_,j,p) in enumerate(arr):
        if abs(i-j)%2 != p:
            break
    else:
        inv = 0
        for j in range(1,N):
            for i in range(j):
                if arr[j][1] < arr[i][1]:
                    inv += 1
        ans = min(ans, inv)
print(-1 if ans==INF else ans)

Submission status: Wrong Answer

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

INF = float('inf')
ans = INF
for k in range(1<<N):
    arr = []
    for i,(a,b) in enumerate(zip(A,B)):
        if k&(1<<i):
            arr.append((a,i,0))
        else:
            arr.append((b,i,1))
    arr.sort()
    inv = 0
    for i,(_,j,p) in enumerate(arr):
        _inv = abs(i-j)
        if _inv%2 != p:
            break
        inv += _inv
    else:
        ans = min(ans, inv)
print(-1 if ans==INF else ans//2)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
inf=100000000
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],x[j][1],x[j][2]] for j in range(n)]
    x.sort()
    for j in range(n):
        if abs(x[j][1]-j)%2!=x[j][2]:
            break
    else:
        cnt=0
        f=1 #隣接した要素が昇順になっていないものが存在する
        while f:
            f=0
            for k in range(n-1):
                if y[n-k-1]<y[n-k-2]:
                    y[n-k-1],y[n-k-2]=y[n-k-2],y[n-k-1]
                    f=1
                    cnt+=1
                if cnt>=ans:
                    break
            if cnt>=ans:
                    break
        else:
            ans=cnt
    #print(x)
    #print(ans)

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

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):
    if L[j][0] > T[j]:
      for k in range(j + 1 + L[j][1], N, 2):
        if D[k] == 0 and L[j][0] == T[k]:
          D[k] = 1
          cnt += k - j
          break
      else:
        break
    else:
      for k in range(((j % 2) + (1 - L[j][1])) % 2, N, 2):
        if D[k] == 0 and L[j][0] == T[k]:
          D[k] = 1
          if k > j:
            cnt += k - j
          break
      else:
        break
  else:
    ans = min(ans, cnt)

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

Submission status: Wrong Answer

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
    for i in range(N):
        # 偶奇位置を交互に取り出す
        a, j = A1[i%2].pop()
        # 元の位置からの移動距離
        cnt += abs(i - j)
        A2[i] = a
    # ソート済と一致すればOK
    if A2 == sorted(A2):
        ans = min(ans, cnt)
if ans == INF:
    print(-1)
else:
    # 移動距離が両方向カウントされるので/2する
    print(ans // 2)