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:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = float("inf")
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)
for i in range(pow(2, N)):
  x = []
  l = []
  c = 0
  for j in range(N):
    if i & (1 << j):
      c += 1
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  if c % 2: continue
  y = sorted(x, key = lambda x: x[0])
  z = -1
  #print(y, i)
  for j in range(N):
    t = abs(j - y[j][1])
    #print(i & (1 << y[j][1]) > 0, t)
    if i & (1 << j) > 0:
      if t % 2:
        z = max(z, t)
      else:
        z = -1
        break
    else:
      if t % 2 == 0:
        z = max(z, t)
      else:
        z = -1
        break
  if z == -1: continue
  z = 0
  fwk = BIT(51)
  for i in range(N):
    z += fwk.get(x[i][0] + 1, 50)
    fwk.add(x[i][0], 1)
  res = min(res, z)

  
if res != float("inf"): print(res)
else: print(-1)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**n:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

def tentou(X):
  ret=0
  BIT=[0]*nn
  BIT.insert(0,0)
  for i1 in range(n):
    x=X[i1]+1
    ret+=i1-bitsum(BIT,x)
    bitadd(BIT,x,1)
  return ret
N=[int(i) for i in range(n)]
nn=2**n
ans=float("inf")
for _ in range(n//2):
  for com in itertools.combinations(N,2*_):
    i=0
    for ura in com:
      i+=2**ura
  E,O=[],[]
  for j in range(n):
    if i&(1<<j)==0:
      if j%2==0:
        E.append(A[j]*100+j)
      else:
        O.append(A[j]*100+j)
    else:
      if j%2==0:
        O.append(B[j]*100+j)
      else:
        E.append(B[j]*100+j)
  if len(E)!=(n+1)//2:
    continue
  else:
    E.sort()
    O.sort()

    chk=True
    C=[E[0]%100]
    prev=E[0]//100
    for i in range(1,n):
      ii=i//2
      if i%2==0:
        C.append(E[ii]%100)
        if E[ii]//100<prev:
          chk=False
          break
        else:
          prev=E[ii]//100
      else:
        C.append(O[ii]%100)
        if O[ii]//100<prev:
          chk=False
          break
        else:
          prev=O[ii]//100
    
  if chk:
    ans=min(ans,tentou(C))
print(-1 if ans==float("inf") else 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()))
res = float("inf")
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)
for i in range(pow(2, N)):
  x = []
  l = []
  c = 0
  for j in range(N):
    if i & (1 << j):
      c += 1
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  if c % 2: continue
  y = sorted(x, key = lambda x: x[0])
  z = -1
  #print(y, i)
  for j in range(N):
    t = abs(j - y[j][1])
    #print(i & (1 << y[j][1]) > 0, t)
    if i & (1 << j) > 0:
      if t % 2:
        z = max(z, t)
      else:
        z = -1
        break
    else:
      if t % 2 == 0:
        z = max(z, t)
      else:
        z = -1
        break
  if z == -1: continue
  z = 0
  fwk = BIT(50)
  for i in range(N):
    z += fwk.get(x[i][0], 50)
    fwk.add(x[i][0], 1)
  res = min(res, z)

  
if res != float("inf"): print(res)
else: print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import product


def solve(n, a_list, b_list):

    res = 10 ** 9 + 7

    for p in product([0, 1], repeat=n):
        if sum(p) % 2 == 1:
            continue

        r = 0
        q = [0] * n

        c_list = [a for a in a_list]
        for i in range(n):
            if p[i] == 1:
                c_list[i] = b_list[i]
        c_list_s = list(sorted(c_list))

        # r
        for i in range(n - 1):
            for j in range(i + 1, n):
                if c_list[i] > c_list[j]:
                    r += 1
                    q[i] += 1
                    q[j] += 1

        used = [0] * n
        d = []
        for k in range(n):
            for i in range(n):
                if c_list[i] == c_list_s[k] and not used[i]:
                    used[i] = 1
                    j = i
                    break
            d.append((p[j] + q[j]) % 2)
            if k == n - 1:
                if sum(d) % 2 == 0:
                    for i in range(len(d)):
                        if d[i] == 1:
                            r += 1
                            d[i + 1] = 1 - d[i + 1]
                else:
                    r += 10 ** 9 + 7
                d = []
            elif c_list_s[k] != c_list_s[k + 1]:
                if sum(d) % 2 == 0:
                    for i in range(len(d)):
                        if d[i] == 1:
                            r += 1
                            d[i + 1] = 1 - d[i + 1]
                else:
                    r += 10 ** 9 + 7
                d = []

        res = min(res, r)
    # print(res)
    if res < 10 ** 9 + 7:
        return res
    else:
        return -1


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    res = solve(n, a_list, b_list)
    print(res)


def test():
    assert solve(3, [3, 4, 3], [3, 2, 3]) == 1
    assert solve(2, [2, 1], [1, 2]) == -1
    assert solve(4, [1, 2, 3, 4], [5, 6, 7, 8]) == 0


if __name__ == "__main__":
    test()
    main()

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()))
res = float("inf")
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)
for i in range(pow(2, N)):
  x = []
  l = []
  c = 0
  for j in range(N):
    if i & (1 << j):
      c += 1
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  if c % 2: continue
  y = sorted(x, key = lambda x: x[0])
  z = -1
  #print(y, i)
  for j in range(N):
    t = abs(j - y[j][1])
    #print(i & (1 << y[j][1]) > 0, t)
    if i & (1 << j) > 0:
      if t % 2:
        z = max(z, t)
      else:
        z = -1
        break
    else:
      if t % 2 == 0:
        z = max(z, t)
      else:
        z = -1
        break
  if z == -1: continue
  z = 0
  fwk = BIT(50)
  for i in range(N):
    z += fwk.sum(x[i][0] - 1)
    fwk.add(x[i][0], 1)
  res = min(res, z)

  
if res != float("inf"): print(res)
else: print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import math

def first(i,a,b):
    if i%2==0: return [a,b,i]
    else: return [b,a,i]

def chk(a,b):
    if m==l:
        for i in range(m-1):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0
        if a[m-1][0]>b[m-1][0]: return 0
            
    else:
        for i in range(l):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0

    return 1

def cal(a,b):
    w=[]
    if m==l:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
    else:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
        w.append(a[m-1][1])
    return w
        


n=int(input())
m,l=n-n//2,n//2
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if n==1:
    print(0)
    sys.exit()

x=[first(i,a[i],b[i]) for i in range(n)]

p=[i for i in range(n)]
ans=1000000

for q in itertools.combinations(p,m):
    tmpa,tmpb=[],[]
    for i in range(n):
        if i in q: tmpa.append([ x[i][0],x[i][2] ])
        else: tmpb.append([x[i][1],x[i][2]])
    tmpa.sort()
    tmpb.sort()


    if chk(tmpa,tmpb)==1:
        t=cal(tmpa,tmpb)
        tans=0
        for i in range(n):
            for j in range(i):
                if a[j]>a[i]: tans+=1
        ans=min(ans,tans)

print(ans if ans<=n*(n-1)/2 else -1)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import math

def first(i,a,b):
    if i%2==0: return [a,b,i]
    else: return [b,a,i]

def chk(a,b):
    if m==l:
        for i in range(m-1):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0
        if a[m-1][0]>b[m-1][0]: return 0
            
    else:
        for i in range(l):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0

    return 1

def cal(a,b):
    w=[]
    if m==l:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
    else:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
        w.append(a[m-1][1])
    return w
        


n=int(input())
m,l=n-n//2,n//2
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if n==1:
    print(0)
    sys.exit()

x=[first(i,a[i],b[i]) for i in range(n)]

p=[i for i in range(n)]
ans=1000000

for q in itertools.combinations(p,m):
    tmpa,tmpb=[],[]
    for i in range(n):
        if i in q: tmpa.append([ x[i][0],x[i][2] ])
        else: tmpb.append([x[i][1],x[i][2]])
    tmpa.sort()
    tmpb.sort()


    if chk(tmpa,tmpb)==1:
        s=[0 for i in range(n)]
        t=cal(tmpa,tmpb)
        tans=0
        for i in range(n-1):
            for j in range(i+1,n):
                if a[i]>a[j]: tans+=1
        ans=min(ans,tans)

print(ans if ans<=n*(n-1)/2 else -1)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import math

def first(i,a,b):
    if i%2==0: return [a,b,i]
    else: return [b,a,i]

def chk(a,b):
    if m==l:
        for i in range(m-1):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0
        if a[m-1][0]>b[m-1][0]: return 0
            
    else:
        for i in range(l):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0

    return 1

def cal(a,b):
    w=[]
    if m==l:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
    else:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
        w.append(a[m-1][1])
    return w
        


n=int(input())
m,l=n-n//2,n//2
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if n==1:
    print(0)
    sys.exit()

x=[first(i,a[i],b[i]) for i in range(n)]
x.sort()

p=[i for i in range(n)]
ans=1000000

for q in itertools.combinations(p,m):
    tmpa,tmpb=[],[]
    for i in range(n):
        if i in q: tmpa.append([ x[i][0],x[i][2] ])
        else: tmpb.append([x[i][1],x[i][2]])
    tmpb.sort()


    if chk(tmpa,tmpb)==1:
        s=[0 for i in range(n)]
        t=cal(tmpa,tmpb)
        tans=0
        for i in range(n-1):
            for j in range(i+1,n):
                if a[i]>a[j]: tans+=1
        ans=min(ans,tans)

print(ans if ans<=n*(n-1)/2 else -1)

Submission status: Wrong Answer

Solution code:
from itertools import product


def solve(n, a_list, b_list):

    res = 10 ** 9 + 7

    for p in product([0, 1], repeat=n):
        if sum(p) % 2 == 1:
            continue

        r = 0
        q = [0] * n

        c_list = [a for a in a_list]
        for i in range(n):
            if p[i] == 1:
                c_list[i] = b_list[i]
        c_list_s = list(sorted(c_list))

        # r
        for i in range(n - 1):
            for j in range(i + 1, n):
                if c_list[i] > c_list[j]:
                    r += 1
                    q[i] += 1
                    q[j] += 1

        used = [0] * n
        d = 0
        for k in range(n):
            for i in range(n):
                if c_list[i] == c_list_s[k] and not used[i]:
                    used[i] = 1
                    j = i
                    break
            if (p[j] + q[j]) % 2:
                d += 1
            if k == n - 1:
                if d % 2 == 0:
                    r += d // 2
                else:
                    r += 10 ** 9 + 7
                d = 0
            elif c_list_s[k] != c_list_s[k + 1]:
                if d % 2 == 0:
                    r += d // 2
                else:
                    r += 10 ** 9 + 7
                d = 0

        res = min(res, r)
    # print(res)
    if res < 10 ** 9 + 7:
        return res
    else:
        return -1


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    res = solve(n, a_list, b_list)
    print(res)


def test():
    assert solve(3, [3, 4, 3], [3, 2, 3]) == 1
    assert solve(2, [2, 1], [1, 2]) == -1
    assert solve(4, [1, 2, 3, 4], [5, 6, 7, 8]) == 0


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import math

def first(i,a,b):
    if i%2==0: return [a,b,i]
    else: return [b,a,i]

def chk(a,b):
    if m==l:
        for i in range(m-1):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0
        if a[m-1][0]>b[m-1][0]: return 0
            
    else:
        for i in range(l):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0

    return 1

def cal(a,b):
    w=[]
    if m==l:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
    else:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
        w.append(a[m-1][1])
    return w
        


n=int(input())
m,l=n-n//2,n//2
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if n==1:
    print(0)
    sys.exit()

x=[first(i,a[i],b[i]) for i in range(n)]
x.sort()


m=math.ceil(n/2)
p=[i for i in range(n)]
ans=1000000

for q in itertools.combinations(p,m):
    tmpa,tmpb=[],[]
    for i in range(n):
        if i in q: tmpa.append([ x[i][0],x[i][2] ])
        else: tmpb.append([x[i][1],x[i][2]])
    tmpb.sort()


    if chk(tmpa,tmpb)==1:
        s=[0 for i in range(n)]
        t=cal(tmpa,tmpb)
        tans=0
        for i in range(n-1):
            for j in range(i+1,n):
                if a[i]>a[j]: tans+=1
        ans=min(ans,tans)

print(ans if ans<=n*(n-1)/2 else -1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product

def solve(N: int, A: "List[int]", B: "List[int]"):

    AB = list(zip(A,B))
    answer = 10**18

    #0が表,1が裏返す
    for bit in product([0,1],repeat=N):
        one_count = bit.count(1)
        if one_count%2 == 1:
            continue

        num_list = []
        #(数字,表か裏か,元々のindex)
        for i in range(N):
            num_list.append((AB[i][bit[i]],bit[i],i))

        num_list.sort(key= lambda x: (x[0]))

        move_dist = 0
        for i in range(N):
            for j in range(i+1,N):
                if num_list[i][2] > num_list[j][2]:
                    move_dist+=1

        else: ## 可能な移動である
            answer = min(answer,move_dist)

    if answer == 10**18:
        print(-1)
    else:
        print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import math

def first(i,a,b):
    if i%2==0: return [a,b,i]
    else: return [b,a,i]

def chk(a,b):
    if m==l:
        for i in range(m-1):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0
        if a[m-1][0]>b[m-1][0]: return 0
            
    else:
        for i in range(l):
            if a[i][0]>b[i][0] or b[i][0]>a[i+1][0]:
                return 0

    return 1

def cal(a,b):
    w=[]
    if m==l:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
    else:
        for i in range(l):
            w+=[a[i][1],b[i][1]]
        w.append(a[m-1][1])
    return w
        


n=int(input())
m,l=n-n//2,n//2
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if n==1:
    print(0)
    sys.exit()

x=[first(i,a[i],b[i]) for i in range(n)]
x.sort()


m=math.ceil(n/2)
p=[i for i in range(n)]
ans=1000000

for q in itertools.combinations(p,m):
    tmpa,tmpb=[],[]
    for i in range(n):
        if i in q: tmpa.append([ x[i][0],x[i][2] ])
        else: tmpb.append([x[i][1],x[i][2]])
    tmpb.sort()


    if chk(tmpa,tmpb)==1:
        s=[0 for i in range(n)]
        t=cal(tmpa,tmpb)
        tans=0
        for i in range(n-1):
            for j in range(i+1,n):
                if a[i]>a[j]: tans+=1
        ans=min(ans,tans)

print(ans if ans<1000000 else -1)

Submission status: Wrong Answer

Solution code:
from itertools import product


def solve(n, a_list, b_list):

    res = 10 ** 9 + 7

    for p in product([0, 1], repeat=n):
        if sum(p) % 2 == 1:
            continue
        r = 0

        c_list = [a for a in a_list]
        for i in range(n):
            if p[i] == 1:
                c_list[i] = b_list[i]
        c_list_s = list(sorted(c_list))

        # r
        for i in range(n - 1):
            for j in range(i + 1, n):
                if c_list[i] > c_list[j]:
                    r += 1

        used = [0] * n
        d = 0
        for k in range(n):
            for i in range(n):
                if c_list[i] == c_list_s[k] and not used[i]:
                    used[i] = 1
                    j = i
                    break
            if (j - k + p[j]) % 2:
                d += 1
            if k == n - 1:
                if d % 2 == 0:
                    r += d // 2
                else:
                    r += 10 ** 9 + 7
                d = 0
            elif c_list_s[k] != c_list_s[k + 1]:
                if d % 2 == 0:
                    r += d // 2
                else:
                    r += 10 ** 9 + 7
                d = 0

        res = min(res, r)
    # print(res)
    if res < 10 ** 9 + 7:
        return res
    else:
        return -1


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    res = solve(n, a_list, b_list)
    print(res)


def test():
    assert solve(3, [3, 4, 3], [3, 2, 3]) == 1
    assert solve(2, [2, 1], [1, 2]) == -1
    assert solve(4, [1, 2, 3, 4], [5, 6, 7, 8]) == 0


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product


def solve(n, a_list, b_list):

    res = 10 ** 9 + 7

    for p in product([0, 1], repeat=n):
        if sum(p) % 2 == 1:
            continue
        r = 0

        c_list = [a for a in a_list]
        for i in range(n):
            if p[i] == 1:
                c_list[i] = b_list[i]
        c_list_s = list(sorted(c_list))

        # r
        for i in range(n - 1):
            for j in range(i + 1, n):
                if c_list[i] > c_list[j]:
                    r += 1

        used = [0] * n
        d = 0
        for k in range(n):
            for i in range(n):
                if c_list[i] == c_list_s[k] and not used[i]:
                    used[i] = 1
                    j = i
                    break
            if (j - k + p[j]) % 2:
                d += 1
            if k == n - 1:
                if d % 2 == 0:
                    r += d // 2
                else:
                    r += 10 ** 9 + 7
            elif c_list_s[k] != c_list_s[k + 1]:
                if d % 2 == 0:
                    r += d // 2
                else:
                    r += 10 ** 9 + 7

        res = min(res, r)
    # print(res)
    if res < 10 ** 9 + 7:
        return res
    else:
        return -1


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    res = solve(n, a_list, b_list)
    print(res)


def test():
    assert solve(3, [3, 4, 3], [3, 2, 3]) == 1
    assert solve(2, [2, 1], [1, 2]) == -1
    assert solve(4, [1, 2, 3, 4], [5, 6, 7, 8]) == 0


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**n:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
nn=2**n
ans=float("inf")
for i in range(nn):
  E,O=[],[]
  for j in range(n):
    if i&(1<<j)==0:
      if j%2==0:
        E.append(A[j]*100+j)
      else:
        O.append(A[j]*100+j)
    else:
      if j%2==0:
        O.append(B[j]*100+j)
      else:
        E.append(B[j]*100+j)

  E.sort()
  O.sort()

  chk=True
  if len(E)!=(n+1)//2:
    chk=False
  else:
    C=[E[0]]
    for i in range(1,n):
      if i%2==0:
        C.append(E[i//2])
        
      else:
        C.append(O[i//2])
      if C[-1]<C[-2]:
          chk=False
          break
    
  if chk:
    ct=0
    BIT=[0]*nn
    BIT.insert(0,0)
    for i1 in range(n):
      c=(C[i1]%100)+1
      ct+=i1-bitsum(BIT,c)
      bitadd(BIT,c,1)


    
    ans=min(ans,ct)
print(-1 if ans==float("inf") else ans)

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0 for _ in range(n+1)]
    def sum(self,index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res
    def add(self,index,x): #1-index
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

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

ans = 10**18

for i in range(2**N):
    C = []
    bcount = 0
    for j in range(N):
        if ((i >> j) & 1):
            C.append([A[j],j,0])
        else:
            C.append([B[j],j,1])
            bcount += 1
    if bcount %2 != 0:
        continue

    C.sort()

    check = True
    for i in range(N):
        if (C[i][1]+C[i][2])%2 != i%2:
            flag = False
            j = 1
            while i+j < N and C[i][0]==C[i+j][0]:
                if (C[i+j][1]+C[i+j][2])%2 == i%2:
                    C[i][0],C[i+j][0] = C[i+j][0],C[i][0]
                    C[i][1],C[i+j][1] = C[i+j][1],C[i][1]
                    C[i][2],C[i+j][2] = C[i+j][2],C[i][2]
                    flag = True
                    break
                j += 1
            if flag:
                continue
            else:
                check = False
                break
    if not check:
        continue
    else:
        count = 0
        bit = BinaryIndexedTree(N+1)

        for k in range(N):
            bit.add(C[k][1]+1,1)
            count += k+1-bit.sum(C[k][1]+1)

        ans = min(ans,count)

print(ans if ans != 10**18 else -1)

Submission status: Wrong Answer

Solution code:
from itertools import product as p
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
an=float("INF")
def f(x):
    s=0
    while x:
        s+=q[x]
        x-=x&-x
    return s
def g(x):
    while x<=51:
        q[x]+=1
        x+=x&-x
for i in p([0,1], repeat=n):
    if sum(i)%2==0:
        c=[]
        for h in range(n):
            if i[h]:
                c.append([b[h],h,1])
            else:
                c.append([a[h],h,0])
        d=sorted(c)
        q=[0]*51
        x,ans=0,0
        for s in range(n):
            if (d[s][1]-s)%2!=d[s][2]:
                x=1
                break
            else:
                g(c[s][0])
                ans+=s+1-f(c[s][0])
        else:
            an=min(an,ans)
print(-1 if an==float("INF") else an)

Submission status: Wrong Answer

Solution code:
from itertools import product


def solve(n, a_list, b_list):
    res = 10 ** 9 + 7
    v_dict_from = dict()
    v_dict_to = dict()

    for p in product([0, 1], repeat=n):
        if sum(p) % 2 == 1:
            continue
        r = 0

        c_list = [a for a in a_list]
        for i in range(n):
            if p[i] == 1:
                c_list[i] = b_list[i]
        c_list_s = list(sorted(c_list))
        for i in range(n - 1):
            for j in range(i + 1, n):
                if c_list[i] > c_list[j]:
                    r += 1

        for v in range(1, 51):
            v_dict_from[v] = []
            v_dict_to[v] = []
        for i in range(n):
            v_dict_from[c_list[i]].append(i)
            v_dict_to[c_list_s[i]].append(i)
        # print(v_dict_from)
        # print(v_dict_to)
        for v in range(1, 51):
            d = 0
            for j, k in zip(list(sorted(v_dict_from[v])), v_dict_to[v]):
                if (j - k + p[j]) % 2:
                    d += 1
            if d % 2 == 0:
                r += d // 2
            else:
                r += 10 ** 9 + 7

        res = min(res, r)
    # print(res)
    if res < 10 ** 9 + 7:
        return res
    else:
        return -1


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    res = solve(n, a_list, b_list)
    print(res)


def test():
    assert solve(3, [3, 4, 3], [3, 2, 3]) == 1
    assert solve(2, [2, 1], [1, 2]) == -1
    assert solve(4, [1, 2, 3, 4], [5, 6, 7, 8]) == 0


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**n:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
nn=2**n
ans=float("inf")
for i in range(nn):
  E,O=[],[]
  for j in range(n):
    if i&(1<<j)==0:
      if j%2==0:
        E.append(A[j]*10000+j*100+0)
      else:
        O.append(A[j]*10000+j*100+0)
    else:
      if j%2==0:
        O.append(B[j]*10000+j*100+1)
      else:
        E.append(B[j]*10000+j*100+1)

  E.sort()
  O.sort()
  C=[]

  chk=True
  if len(E)!=(n+1)//2:
    chk=False
  else:
    for i in range(n):
      if i%2==0:
        C.append(E[i//2])
      else:
        C.append(O[i//2])
    for ii in range(n-1):
      if C[ii]/10000>C[ii+1]//10000:
        chk=False
        break
    
    if chk:
      ct=0
      BIT=[0]*nn
      BIT.insert(0,0)
      for i1 in range(n):
        c=(C[i1]%10000)//100+1
        ct+=i1-bitsum(BIT,c)
        bitadd(BIT,c,1)


    
      ans=min(ans,ct)
print(-1 if ans==float("inf") else ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [int(b) for b in input().split()]
    
    minmove = 1000000000
    for i in itertools.product("01", repeat = N):
        back = 0
        Num = []
        original = dict()
        for j in range(N):
            if i[j] == "0": n = A[j]
            else:
                n = B[j]
                back += 1
            if n not in original: original[n] = {j}
            else: original[n] |= {j}
            Num.append(n)
        if back % 2 > 0: continue
        Num.sort() #実現したい数列
        
        move = 0
        swapped = []
        for j, n in enumerate(Num): #このソートが実現できるか
            for o in sorted(original[n]):
                if abs(j - o) % 2 == 0 and A[o] == n:
                    original[n] -= {o}
                    swapped.append(o)
                    break
                elif abs(j - o) % 2 == 1 and B[o] == n:
                    original[n] -= {o}
                    swapped.append(o)
                    break
            else: #実現できない
                break
        else: #実現できるため、操作回数を求める
            appeared = []
            for n in swapped:
                for k in appeared:
                    if k > n: move += 1
                appeared.append(n)
            minmove = min(minmove, move)

    if minmove == 1000000000: print(-1)
    else: print(minmove)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import copy

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

ans = float("inf")
def dfs(i, count, L):
    global ans
    print("i:{}, count:{}, L:{}".format(i, count, L))
    if i == N-1:
        for i in range(N-1):
            if L[i] > L[i+1]:
                return
        ans = min(ans, count)
    else:
        LCopy = copy.deepcopy(L)
        dfs(i+1, count, LCopy)
        print("aaa")
        LCopy[i] = copy.deepcopy(B[i+1])
        LCopy[i+1] = copy.deepcopy(B[i])
        dfs(i+1, count+1, LCopy)

dfs(0, 0, A)
if ans == float("inf"):
    ans = -1
print(ans)