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: Runtime Error

Solution code:
def main():
    from itertools import combinations
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    cc = combinations(range(n), (n-1)//2+1)
    m = 10**9
    for c in cc:
        memo1 = []
        memo2 = []
        for i in c:
            if i % 2 == 0:
                memo1.append((a[i], i))
            else:
                memo1.append((b[i], i))
        for i in set(range(n))-set(c):
            if i % 2 == 1:
                memo2.append((a[i], i))
            else:
                memo2.append((b[i], i))
        memo1.sort()
        memo2.sort()
        memo = []
        for i in range(n//2):
            memo.append(memo1[i])
            memo.append(memo2[i])
        if n % 2 == 1:
            memo.append(memo1[i+1])
        flag = 0
        for i in range(n-1):
            if memo[i][0] > memo[i+1][0]:
                flag = 1
                break
        if flag == 1:
            continue
        memo = [i for j, i in memo]
        cnt = 0
        for i in range(n-1):
            for j in range(i+1, n):
                if memo[i] > memo[j]:
                    cnt += 1
        m = min(cnt, m)
    if m == 10**9:
        print(-1)
    else:
        print(m)


main()

Submission status: Runtime Error

Solution code:
def main():
    from itertools import combinations
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    cc = combinations(range(n), (n-1)//2+1)
    m = -1
    for c in cc:
        memo1 = []
        memo2 = []
        for i in c:
            if i % 2 == 0:
                memo1.append((a[i], i))
            else:
                memo1.append((b[i], i))
        for i in set(range(n))-set(c):
            if i % 2 == 1:
                memo2.append((a[i], i))
            else:
                memo2.append((b[i], i))
        memo1.sort()
        memo2.sort()
        memo = []
        for i in range(n//2):
            memo.append(memo1[i])
            memo.append(memo2[i])
        if n % 2 == 1:
            memo.append(memo1[i+1])
        flag = 0
        for i in range(n-1):
            if memo[i][0] > memo[i+1][0]:
                flag = 1
                break
        if flag == 1:
            continue
        memo = [i for j, i in memo]
        cnt = 0
        for i in range(n-1):
            for j in range(i+1, n):
                if a[i] > a[j]:
                    cnt += 1
        m = max(cnt, m)
    print(m)


main()

Submission status: Runtime Error

Solution code:
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 10**9


def bubble_sort(arr):
    change = True
    num = 0
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
                num += 1
    return num


for i in range(2**n):
    even = []
    odd = []
    for j in range(n):
        x = (i >> j) % 2
        if j % 2 == 0:
            if x == 0:
                even.append((a[j], j))
            else:
                odd.append((b[j], j))
        else:
            if x == 0:
                odd.append((a[j], j))
            else:
                even.append((b[j], j))
    even.sort()
    odd.sort()
    check = True
    order = []
    new = []
    for j in range(n//2):
        order.append(even[j][1])
        order.append(odd[j][1])
        new.append(even[j][0])
        new.append(odd[j][0])
    if n % 2 != 0:
        new.append(even[-1][0])
        order.append(even[-1][1])
    for j in range(n-1):
        if new[j] > new[j+1]:
            check = False
    if not check:
        continue
    x = bubble_sort(order)
    ans = min(ans, x)
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=10**9
def bubble_sort(arr):
    change = True
    num=0
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
                num+=1
    return num
for i in range(2**n):
    even=[]
    odd=[]
    for j in range(n):
        x=(i>>j)%2
        if j%2==0:
            if x==0:
                even.append((a[j],j))
            else:
                odd.append((b[j],j))
        else:
            if x==0:
                odd.append((a[j],j))
            else:
                even.append((b[j],j))
    #if len(odd)!=n//2:
    #    continue
    even.sort()
    odd.sort()
    check=True
    order=[]
    new=[]
    for j in range(n//2):
        order.append(even[j][1])
        order.append(odd[j][1])
        new.append(even[j][0])
        new.append(odd[j][0])
    if n%2!=0:
        new.append(even[-1][0])
        order.append(even[-1][1])
    for j in range(n-1):
        if new[j]>new[j+1]:
            check=False
    if not check:
        continue
    x=bubble_sort(order)
    ans=min(ans,x)
if ans==10**9:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

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]*256
  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+1):
  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: Runtime Error

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]*128
  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+1):
  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: Runtime Error

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]*64
  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+1):
  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: Runtime Error

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]*128
  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+1):
  for com in itertools.combinations(N,2*_):
    E,O=[],[]
    for j in range(n):
      if j not in com:
        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: Runtime Error

Solution code:
import bisect
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 10**9+7
for i in range(2**N):
    card = [[],[]]
    num = []
    iii = i
    for j in range(N):
        if i&1:
            num.append(B[j])
            card[(j+1)%2].append(j)
        else:
            num.append(A[j])
            card[(j)%2].append(j)
        i >>= 1
    if len(card[0]) != N//2:
        continue
    card[0].sort(key=lambda x:[num[x],x])
    card[1].sort(key=lambda x:[num[x],x])
    hoge = []
    for i in range(N):
        hoge.append(card[i%2][i//2])
    flag = True
    for i in range(N-1):
        if num[hoge[i]] > num[hoge[i+1]]:
            flag = False
    if flag:
        huga = []
        count = 0
        for i in range(N):
            l = bisect.bisect_left(huga,hoge[i])
            huga.insert(l,hoge[i])
            count += i-l
        if count < ans:
            ans = count
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

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]*64
  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+1):
  for com in itertools.combinations(N,2*_):
    E,O=[],[]
    for j in range(n):
      if j not in com:
        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: Runtime Error

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

ans = 1 << 100
for m in range(1<<N):
    if bin(m).count("1") & 1: continue
    C = [[], []]
    for i in range(N):
        p = m >> i & 1
        q = p + i & 1
        C[q].append(((A[i] if p == 0 else B[i]) << 5) + i)
    if len(C[1]) != N // 2: continue
    C[0].sort()
    C[1].sort()
    CC = [C[i&1][i//2] for i in range(N)]
    for i in range(1, N):
        if CC[i-1] >> 5 > CC[i] >> 5: break
    else:
        CCC = [c % 32 for c in CC]
        ans = min(ans, chk(CCC))
print(ans if ans < 1 << 100 else -1)

Submission status: Runtime Error

Solution code:
import copy
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
I=0
flag=0
anslist=[]
jh=[0]
def play(ca,cb,I,lis):
  if I==n-1:
    anslist.append([ca,lis])
    if sorted(I)==I:
      flag=1
      z=sum(lis)
    if kai>z:
      kai=z
    return kai,flag
  else:
    sa=copy.deepcopy(ca)
    sb=copy.deepcopy(cb)
    ll=lis+[0]
    play(sa,sb,I+1,ll)
    ls=lis+[1]
    ta=copy.deepcopy(ca)
    tb=copy.deepcopy(cb)
    s,t=sa[I],sb[I]
    ta[I],tb[I]=sb[I+1],sa[I+1]
    tb[I+1],ta[I+1]=s,t
    play(ta,tb,I+1,ls)
play(a,b,0,jh)
kai=18

if flag==0:
  print(-1)
else:
  print(kai)

Submission status: Runtime Error

Solution code:
import numpy as np
from itertools import combinations

n = int(input())
rs = np.array(list(map(int, input().split())))
bs = np.array(list(map(int, input().split())))
_rs = np.array([rs[i] if i %2 == 0 else bs[i] for i in range(n)])
_bs = np.array([rs[i] if i %2 ==1 else bs[i] for i in range(n)])
rs=_rs
bs=_bs
c = [(r, s, i) for i, (r, s) in enumerate(zip(rs, bs))]

h = n // 2
if n % 2:
    h += 1
all_ = np.arange(n)
MAX=10000
res = MAX
for al in combinations(range(n), h):
    idx = np.full(n, False)
    idx[list(al)] = True
    rl = sorted([(r, i) for r, i in zip(rs[idx], al)])
    bl = sorted([(b,i) for b, i in zip(bs[~idx], all_[~idx])])
    v = []
    for i in range(0, n):
        if i % 2:
            v.append(bl.pop(0))
        else:
            v.append(rl.pop(0))
    l = 0
    buf = -100
    ok=True
    for i,vv in enumerate(v):
        l += abs(i - vv[1])
        if buf > vv[0]:
            ok=False
            break
        buf = vv[0]
    if ok:
        res = min(res, l//2)
    
if res == MAX:
    print(-1)
else:
    print(res)

Submission status: Runtime Error

Solution code:
N, K, S = map(int, input().split())
INF = 10**9

if K == 0:
    if S == INF:
        print(' '.join([str(INF-1) for _ in range(N)]))
    else:
        print(' '.join([str(INF) for _ in range(N)]))
    exit()

if S == INF:
    ans = [INF] * K
    ans.extend([INF-1] * (N-K))
else:
    ans = [S] * K
    ans.extend([INF] * (N-K))
print(' '.join([str(x) for x in ans]))

Submission status: Runtime Error

Solution code:
import numpy as np
from itertools import combinations

n = int(input())
rs = np.array(list(map(int, input().split())))
bs = np.array(list(map(int, input().split())))
_rs = np.array([rs[i] if i %2 == 0 else bs[i] for i in range(n)])
_bs = np.array([rs[i] if i %2 ==1 else bs[i] for i in range(n)])
rs=_rs
bs=_bs
c = [(r, s, i) for i, (r, s) in enumerate(zip(rs, bs))]

h = n // 2
if n % 2:
    h += 1
all_ = np.arange(n)
res = 100000
for al in combinations(range(n), h):
    idx = np.full(n, False)
    idx[list(al)] = True
    rl = sorted([(r, i) for r, i in zip(rs[idx], al)])
    bl = sorted([(b,i) for b, i in zip(bs[~idx], all_[~idx])])
    v = []
    for i in range(0, n):
        if i % 2:
            v.append(bl.pop(0))
        else:
            v.append(rl.pop(0))
    l = 0
    buf = -100
    ok=True
    for i,vv in enumerate(v):
        l += abs(i - vv[1])
        if buf > vv[0]:
            ok=False
            break
    if ok:
        res = min(res, l)
    
print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1


def babble_sort(arr):
    """ バブルソート """
    length = len(arr)
    count=0
    data=[i for i in range(length)]
    swap=[0]*length

    for i in range(length):
        # 3. 走査範囲を前からひとつ狭める
        for j in reversed(range(i+1, length)):
            # 1. 後ろから順に隣り合う要素を比較する。
            if arr[j-1] > arr[j]:
                # 2. 左が右の要素に比べ大きい場合交換する。
                arr[j-1], arr[j] = arr[j], arr[j-1]
                data[j-1], data[j] = data[j], data[j-1]
                swap[data[j]]+=1
                swap[data[j-1]]+=1
                count+=1
    return count,swap

def f(n):
    count=0
    while n:
        count+=n%2
        n//=2
    return count

n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
for bit in range(2**n):
    # if bit==3:
    #     print(f(bit))
    if f(bit)%2!=0:
        continue
    tar=[0]*n
    data=[0]*n
    for i in range(n):
        if (bit>>i & 1):
            tar[i]=B[i]; data[i]=1
        else:
            tar[i]=A[i]
    tmp,swap=babble_sort(tar[:])
    S=[[]]*51
    # if bit==3:
    #     print(data,swap,tar,bit,sep="\n")
    for i in range(n):
        if swap[i]%2!=data[i]:
            S[tar[i]].append(1)
        else:
            S[tar[i]].append(0)
    for k in range(51):
        for s in range(len(S[k])):
            if S[k][s]==1:
                for t in range(s+1,len(S),2):
                    if S[k][t]==1:
                        S[k][s]=S[k][t]=0
                        tmp+=t-s
                        break
                else:
                    break

                continue
        else:
            continue
        break
    else:
        mans=min(mans,tmp)
    continue
print(-1 if mans==inf else mans)

Submission status: Runtime Error

Solution code:
N, K, S = map(int, input().split())
INF = 10**9

ans = []
if S == INF:
    ans.extend([INF] * K)
    ans.extend([INF-1] * len(ans))
else:
    ans.extend([S] * K)
    ans.extend([INF] * len(ans))

print(' '.join([str(x) for x in ans]))

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def swap(l):
    cnt = 0
    now = list(range(n))
    for i in range(n):
        c = l[n-i-1]
        n_ind = now.index(c)
        # print(n_ind)
        cnt += abs((n-i-1)-n_ind)
        if (n-i-1)-n_ind == 0:
            continue
        now.remove(c)
        # print(now)
        now.insert(n-i-1,c)
        # print(now)
    return cnt

n = inp()
a = inpl()
b = inpl()
card = []
res = INF
for i in range(n):
    card.append([a[i],b[i],i])
for flag in itertools.combinations(range(n),(n+1)//2):
    # print(flag)
    f = True
    odd_li = []
    odd_ind = [False] * n
    for i,bit in enumerate(flag):
        c = 1 if bit%2 else 0
        odd_li.append([card[bit][c],bit])
        odd_ind[bit] = True
    if not f:
        continue
    odd_li.sort()
    even_li = []
    for i in range(n):
        c = 0 if i%2 else 1
        if not odd_ind[i]:
            even_li.append([card[i][c],i])
    even_li.sort()
    # print(odd_li,even_li)

    for i in range(n//2):
        if odd_li[i][0] <= even_li[i][0]:
            continue
        else:
            f = False
            break
        if i == n//2-1 and n%2==0:
            if odd_li[-1][0] <= even_li[-1][0]:
                continue
            else:
                f = False
                break
    if f:
        after_ind = []
        for i in range(n//2+1):
            after_ind.append(odd_li[i][1])
            if i == n//2 and n%2:
                break
            after_ind.append(even_li[i][1])
        # print(after_ind)
        res = min(res,swap(after_ind))
print(-1 if res == INF else res)

Submission status: Runtime Error

Solution code:
import numpy as np
from itertools import combinations

n = int(input())
rs = np.array(list(map(int, input().split())))
bs = np.array(list(map(int, input().split())))
_rs = np.array([rs[i] if i %2 == 0 else bs[i] for i in range(n)])
_bs = np.array([rs[i] if i %2 ==1 else bs[i] for i in range(n)])
rs=_rs
bs=_bs
c = [(r, s, i) for i, (r, s) in enumerate(zip(rs, bs))]

h = n // 2
if n % 2:
    h += 1
all_ = np.arange(n)
res = 100000
for al in combinations(range(n), h):
    idx = np.full(n, False)
    idx[list(al)] = True
    rl = sorted([(r, i) for r, i in zip(rs[idx], al)])
    bl = sorted([(b,i) for b, i in zip(bs[~idx], all_[~idx])])
    v = []
    for i in range(1, n):
        if i % 2:
            v.append(bl[i])
        else:
            v.append(al[i])
    l = 0
    buf = -100
    ok=True
    for i,vv in enumerate(v):
        l += abs(i - vv[1])
        if buf > vv[0]:
            ok=False
            break
    if ok:
        res = min(res, l)
    
print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1


def babble_sort(arr):
    """ バブルソート """
    length = len(arr)
    count=0
    data=[i for i in range(length)]
    swap=[0]*length

    for i in range(length):
        # 3. 走査範囲を前からひとつ狭める
        for j in reversed(range(i+1, length)):
            # 1. 後ろから順に隣り合う要素を比較する。
            if arr[j-1] > arr[j]:
                # 2. 左が右の要素に比べ大きい場合交換する。
                arr[j-1], arr[j] = arr[j], arr[j-1]
                data[j-1], data[j] = data[j], data[j-1]
                swap[data[j]]+=1
                swap[data[j-1]]+=1
                count+=1
    return count,swap

def f(n):
    count=0
    while n:
        count+=n%2
        n//=2
    return count

n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
for bit in range(2**n):
    # if bit==3:
    #     print(f(bit))
    if f(bit)%2!=0:
        continue
    tar=[0]*n
    data=[0]*n
    for i in range(n):
        if (bit>>i & 1):
            tar[i]=B[i]; data[i]=1
        else:
            tar[i]=A[i]
    tmp,swap=babble_sort(tar[:])
    S=[[]]*51
    # if bit==3:
    #     print(data,swap,tar,bit,sep="\n")
    for i in range(n):
        if swap[i]%2!=data[i]:
            S[tar[i]].append(1)
        else:
            S[tar[i]].append(0)
    for k in range(52):
        for s in range(len(S[k])):
            if S[k][s]==1:
                for t in range(s+1,len(S),2):
                    if S[k][t]==1:
                        S[k][s]=S[k][t]=0
                        tmp+=t-s
                        break
                else:
                    break

                continue
        else:
            continue
        break
    else:
        mans=min(mans,tmp)
    continue
print(-1 if mans==inf else mans)

Submission status: Runtime Error

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

X = [(A[i], i) for i in range(N)]
Y = [(B[i], i) for i in range(N)]


def change(i, j):
    A[i], B[i], A[j], B[j] = B[j], A[j], B[i], A[i]


def count_ones(num):
    num = (num & 0x55555555) + (num >> 1 & 0x55555555)
    num = (num & 0x33333333) + (num >> 2 & 0x33333333)
    num = (num & 0x0F0F0F0F) + (num >> 4 & 0x0F0F0F0F)
    num = (num & 0x00FF00FF) + (num >> 8 & 0x00FF00FF)
    num = (num & 0x0000FFFF) + (num >> 16 & 0x0000FFFF)
    return num


ans = 0

for bi in range(1 << N):
    # bi<<i : iはBが表で終わるか
    if count_ones(bi) % 2 == 1:
        continue
    L = [((B[i], True, i) if bi << i else (A[i], False)) for i in range(N)]


    R = sorted(L)
    ans = 0
    for i in range(N):
        Lval, Lbool, Li = L[i]
        Rval, Rbool, Ri = R[i]
        if Li != Ri:
            ans += 1
            L[Li], L[Ri] = L[Ri], L[Li]
    if L == R:
        print(ans)

print(-1)

Submission status: Runtime Error

Solution code:
from itertools import product
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = defaultdict(int)
d = defaultdict(int)
e = []
f = []
forsort = []
for i in range(n):
  if i%2 == 0:
    c[a[i]] = b[i]
    d[b[i]] = a[i]
    e.append(a[i])
    f.append(b[i])
    forsort.append((a[i],1))
    forsort.append((b[i],2))
  else:
    c[a[i]] = b[i]
    d[b[i]] = a[i]
    e.append(b[i])
    f.append(a[i])
    forsort.append((a[i],2))
    forsort.append((b[i],1))
forsort.sort()
x = [forsort[i][1] for i in range(2*n)]
change = [0]
for i in range(1,2*n):
  if x[i] != x[i-1]:
    change.append(i)
change.append(2*n)
changels = []
for i in range(1,len(change)):
  changels.append([j for j in range(change[i-1],change[i])])
p = x[0]
ans = []
for ls in product(*changels):
  array = []
  cannotuse = defaultdict(int)
  for i in range(len(ls)):
    l = ls[i]
    if (p+i)%2 == 1:
      if cannotuse[forsort[l][0]] != 1:
        array.append(forsort[l][0])
        cannotuse[c[forsort[l][0]]] = 1
        cannotuse[forsort[l][0]] = 1
      else:
        break
    if (p+i)%2 == 0:
      if cannotuse[forsort[l][0]] != 1:
        array.append(forsort[l][0])
        cannotuse[d[forsort[l][0]]] = 1
        cannotuse[forsort[l][0]] = 1
      else:
        break
  if len(array) >= n:
    print(array)
    array = array[:n]
    anstmp = 0
    for ind,i in enumerate(array):
      if ind%2 == 0:
        anstmp += abs(e.index(i)-ind)
      else:
        anstmp += abs(f.index(i)-ind)
    ans.append(anstmp)
    anstmp = 0
if not ans:
  print(-1)
else:
  print(min(ans))

Submission status: Runtime Error

Solution code:
import itertools

N=int(input())
Y=list(map(int,input().split()))
Z=list(map(int,input().split()))
C=list(itertools.product([0,1],repeat=N-1))
y=Y[-1]
z=Z[-2]
ans=N
for i,a in enumerate(C):
  A=Y
  B=Z
  D=[]
  for j in range(N-1):
    if a[j]==0:
      D.append(A[j])
    else:
      D.append(B[j+1])
      A[j+1]=B[j]
      B[j+1]=A[j]
  if a[-1]==0:
    D.append(y)
  else:
    D.append(z)

  if all(D[k+1]-D[k]>=0 for k in range(N-1)):
    x=sum(a)
    ans=min(N,x)

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

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def swap(l):
    cnt = 0
    now = list(range(n))
    for i in range(n):
        c = l[n-i-1]
        n_ind = now.index(c)
        # print(n_ind)
        cnt += abs((n-i-1)-n_ind)
        if (n-i-1)-n_ind == 0:
            continue
        now.remove(c)
        # print(now)
        now.insert(n-i-1,c)
        # print(now)
    return cnt

n = inp()
a = inpl()
b = inpl()
card = []
res = INF
for i in range(n):
    card.append([a[i],b[i],i])

for flag in itertools.combinations(range(n),(n+1)//2):
    # print(flag)
    f = True
    odd_li = []
    odd_ind = [False] * n
    for i,bit in enumerate(flag):
        c = 1 if bit%2 else 0
        odd_li.append([card[bit][c],bit])
        odd_ind[bit] = True
    if not f:
        continue
    odd_li.sort()
    even_li = []
    for i in range(n):
        c = 0 if i%2 else 1
        if not odd_ind[i]:
            even_li.append([card[i][c],i])
    even_li.sort()
    # print(odd_li,even_li)

    for i in range(n//2):
        if odd_li[i][0] <= even_li[i][0] <= odd_li[i+1][0]:
            continue
        else:
            f = False
            break
        if i == n//2-1 and n%2==0:
            if odd_li[-1][0] <= even_li[-1][0]:
                continue
            else:
                f = False
                break
    if f:
        after_ind = []
        for i in range(n//2+1):
            after_ind.append(odd_li[i][1])
            if i == n//2 and n%2:
                break
            after_ind.append(even_li[i][1])
        # print(after_ind)
        res = min(res,swap(after_ind))
print(-1 if res == INF else res)