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: Time Limit Exceeded

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

#a = list(map(int, input().split()))

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

dp = [[[999999,[],0] for _ in range(n)] for _ in range(2**n)]
queset = [[0 for _ in range(n)] for _ in range(2**n)]

dp[0][0][0]=0
que = [[0,0]] #[bit, num of right]
done = 0

while(len(que) > done):
    now = que[done]
    done +=1
    nowBits = ValueToBits(now[0],n)
    sumBits = sum(nowBits) # 既に何枚使ったか
    nowTentou = dp[now[0]][now[1]][0]
    nowCards = []
    for i in range(n):
        if(nowBits[i]==1):
            nowCards.append(i)
    nowRight = dp[now[0]][now[1]][2]
    #if(len(nowCards)>0): print(len(nowCards),nowCards[-1],nowRight)
    for i in range(n):
        if(nowBits[i] == 0):
            # 右端に今加えようとしてるカード i は表か裏か
            UpDown = abs(i-sumBits)%2
            # 右端を加えた集合
            nextValue = now[0] + 2**i
            if(queset[nextValue][i]==0):
                que.append([nextValue, i])
                queset[nextValue][i]=1
            #nextCards = list(nowCards)
            #nextCards.append(i)
            nextRight = A[i] if UpDown==0 else B[i]
            #print(nextCards)
            if(nowRight <= nextRight):
                #print(nowRight,nextRight)
                nextTentou = nowTentou
                for k in nowCards:
                    if(k > i):
                        nextTentou+=1
                #print(dp[nextValue][i][0] , nextTentou)
                if(dp[nextValue][i][0] > nextTentou):
                    dp[nextValue][i][0] = nextTentou
                    #dp[nextValue][i][1] = list(nextCards)
                    dp[nextValue][i][2] = nextRight
                    #print(dp[nextValue][i])
#print()
ans=999999
for i in range(n):
    if(ans > dp[2**n-1][i][0]):
        ans = dp[2**n-1][i][0]
if(ans>99998):
    print(-1)
else:
    print(ans)
#print(len(que))

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

#a = list(map(int, input().split()))

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

dp = [[[999999,[],0] for _ in range(n)] for _ in range(2**n)]

dp[0][0][0]=0
que = [[0,0]] #[bit, num of right]
done = 0

while(len(que) > done):
    now = que[done]
    done +=1
    nowBits = ValueToBits(now[0],n)
    sumBits = sum(nowBits) # 既に何枚使ったか
    nowTentou = dp[now[0]][now[1]][0]
    nowCards = []
    for i in range(n):
        if(nowBits[i]==1):
            nowCards.append(i)
    nowRight = dp[now[0]][now[1]][2]
    #if(len(nowCards)>0): print(len(nowCards),nowCards[-1],nowRight)
    for i in range(n):
        if(nowBits[i] == 0):
            # 右端に今加えようとしてるカード i は表か裏か
            UpDown = abs(i-sumBits)%2
            # 右端を加えた集合
            nextValue = now[0] + 2**i
            que.append([nextValue, i])
            #nextCards = list(nowCards)
            #nextCards.append(i)
            nextRight = A[i] if UpDown==0 else B[i]
            #print(nextCards)
            if(nowRight <= nextRight):
                #print(nowRight,nextRight)
                nextTentou = nowTentou
                for k in nowCards:
                    if(k > i):
                        nextTentou+=1
                #print(dp[nextValue][i][0] , nextTentou)
                if(dp[nextValue][i][0] > nextTentou):
                    dp[nextValue][i][0] = nextTentou
                    #dp[nextValue][i][1] = list(nextCards)
                    dp[nextValue][i][2] = nextRight
                    #print(dp[nextValue][i])
#print()
ans=999999
for i in range(n):
    if(ans > dp[2**n-1][i][0]):
        ans = dp[2**n-1][i][0]
if(ans>99998):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

#a = list(map(int, input().split()))

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

dp = [[[999999,[],0] for _ in range(n)] for _ in range(2**n)]

dp[0][0][0]=0
que = [[0,0]] #[bit, num of right]
done = 0

while(len(que) > done):
    now = que[done]
    done +=1
    nowBits = ValueToBits(now[0],n)
    sumBits = sum(nowBits) # 既に何枚使ったか
    nowTentou = dp[now[0]][now[1]][0]
    nowCards = dp[now[0]][now[1]][1]
    nowRight = dp[now[0]][now[1]][2]
    #if(len(nowCards)>0): print(len(nowCards),nowCards[-1],nowRight)
    for i in range(n):
        if(nowBits[i] == 0):
            # 右端に今加えようとしてるカード i は表か裏か
            UpDown = abs(i-sumBits)%2
            # 右端を加えた集合
            nextValue = now[0] + 2**i
            que.append([nextValue, i])
            nextCards = list(nowCards)
            nextCards.append(i)
            nextRight = A[i] if UpDown==0 else B[i]
            #print(nextCards)
            if(nowRight <= nextRight):
                #print(nowRight,nextRight)
                nextTentou = nowTentou
                for k in nowCards:
                    if(k > i):
                        nextTentou+=1
                #print(dp[nextValue][i][0] , nextTentou)
                if(dp[nextValue][i][0] > nextTentou):
                    dp[nextValue][i][0] = nextTentou
                    dp[nextValue][i][1] = list(nextCards)
                    dp[nextValue][i][2] = nextRight
                    #print(dp[nextValue][i])
#print()
ans=999999
for i in range(n):
    if(ans > dp[2**n-1][i][0]):
        ans = dp[2**n-1][i][0]
if(ans>99998):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

d = {}
for i, ab in enumerate(zip(A, B)):
    d[i] = ab
for p in itertools.permutations(d.keys(), N):
    surface = [d[j][0] if (i - j) % 2 == 0 else d[j][1] for (i, j) in enumerate(p)]
    if surface == sorted(surface):
        ans = 0
        for x, y in itertools.combinations(p, 2):
            if x > y:
                ans += 1
        break
else:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

dp = [[0,0,0]] #bitをset代わりとして用いる [bitset,最後に置いた数字,転倒数]の構成

for loop in range(N): #N枚のカードを置いていく

    ndp = [] #次のループのdp配列
    for ing in dp: #dpの中の各場合について次の場合を調べる

        bit = ing[0]
        lastnum = ing[1]
        revnum = ing[2]

        for i in range(N): #各カードが後ろにおけるかを判定

            if bit & (2**i) > 0: #既に使われてたら飛ばす
                continue

            revnum_add = 0
            for j in range(N): #転倒数がいくつ増えるかの計算
                if j > i and bit&(2**j) > 0:
                    revnum_add += 1

            if i % 2 == loop % 2: #置く位置と初期位置の偶奇が等しければ表
                if A[i] >= lastnum: #置けるなら置く
                    ndp.append([ bit|(2**i) , A[i] ,revnum+revnum_add])

            else:
                if B[i] >= lastnum:
                    ndp.append([ bit|(2**i) , B[i] ,revnum+revnum_add])


    dp = ndp


ans = float("inf") #答えは最小の転倒数
for ing in dp:
    ans = min(ans,ing[2])

if ans == float("inf"):
    ans = -1
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [i for i in range(n)]

def add(k, x):
  while k <= n:
    data[k] += x
    k += k & -k
def get(k):
  s = 0
  while k:
    s += data[k]
    k -= k & -k
  return s
ans = 10 ** 18
for i in itertools.combinations(c,n//2):
  j = list(set(c)-set(i))
  even = sorted([(a[k],k+1) if k % 2 else (b[k],k+1) for k in i])
  odd = sorted([(b[k],k+1) if k % 2 else (a[k],k+1) for k in j])
  prev = -1
  A = []
  for x in range(n):
    Y,X = divmod(x,2)
    if X % 2:
      now0,now1 = even[Y][0],even[Y][1]
    else:
      now0,now1 = odd[Y][0],odd[Y][1]
    if prev > now0:
      break
    else:
      A.append(now1)
    prev = now0
  else:
    data = [0]*(n+1)
    tmp = 0
    for i,z in enumerate(A):
      tmp += (n-1-i) - get(z)
      add(z,1)
    ans = min(ans,tmp)
if ans == 10 ** 18:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def is_non_decreasing(data):
    for i in range(len(data)-1):
        if data[i+1] < data[i]:
            return False
    return True



def search(a,b,depth):
    if is_non_decreasing(a):
        return True
    if depth == 0:
        return False
        
    for i in range(len(a)-1):
        a[i], b[i], a[i+1], b[i+1] = b[i+1], a[i+1], b[i], a[i]

        result = search(a,b,depth-1)

        a[i], b[i], a[i+1], b[i+1] = b[i+1], a[i+1], b[i], a[i]
        
        if result:
            return True
    
    return False
        
def iterative_deepening(a,b):
    for depth in range(0,10):
        result = search(a,b,depth)
        if result:
            print(depth)
            return
    print(-1)
    return



n = int(input())

a = list(map(int,input().split()))
b = list(map(int,input().split()))


iterative_deepening(a,b)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [i for i in range(n)]

def add(k, x):
  while k <= n:
    data[k] += x
    k += k & -k
def get(k):
  s = 0
  while k:
    s += data[k]
    k -= k & -k
  return s
ans = 10 ** 18
for i in itertools.combinations(c,n//2):
  j = list(set(c)-set(i))
  even = sorted([(a[k],k+1) if k % 2 else (b[k],k+1) for k in i])
  odd = sorted([(b[k],k+1) if k % 2 else (a[k],k+1) for k in j])
  prev = -1
  A = []
  for x in range(n):
    if x % 2:
      now = even[x//2][0]
      if prev > now:
        break
      else:
        A.append(even[x//2][1])
    else:
      now = odd[x//2][0]
      if prev > now:
        break
      else:
        A.append(odd[x//2][1])
    prev = now
  else:
    data = [0]*(n+1)
    tmp = 0
    for i,z in enumerate(A):
      tmp += (n-1-i) - get(z)
      add(z,1)
    ans = min(ans,tmp)
if ans == 10 ** 18:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[10**18]*N for _ in range(2**N)]

for i in range(N):
    dp[1<<i][i] = 0

for S in range(2**N):
    cnt = 0
    
    for i in range(N):
        if (S>>i)&1:
            cnt += 1
            
    for i in range(N):
        cost = cnt
        for j in range(N):
            if not (S>>j)&1:
                n1 = A[i] if (i-(cnt-1))%2==0 else B[i]
                n2 = A[j] if (j-cnt)%2==0 else B[j]
                
                if n1>n2:
                    continue
                
                dp[S|(1<<j)][j] = min(dp[S|(1<<j)][j], dp[S][i]+cost)
            else:
                cost -= 1

ans = 10**18

for i in range(N):
    ans = min(ans, dp[2**N-1][i])

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

Submission status: Time Limit Exceeded

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

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

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

        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: Time Limit Exceeded

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+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: Time Limit Exceeded

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+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: Time Limit Exceeded

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

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

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)
  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: Time Limit Exceeded

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)
  if len(E)!=(n+1)//2:
    continue
  else:
    E.sort()
    O.sort()

    chk=True
    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]//100<C[-2]//100:
          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: Time Limit Exceeded

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]//100<C[-2]//100:
          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: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
INF = 1e10
dp = [[INF] * (18) for _ in range(1<<18)]
bitcnt = [0] * (1 << 18)
dp[0][0] = 0

ans = INF

def value(ind, pos):
    if ind % 2 == pos % 2:
        return a[ind]
    else:
        return b[ind]

def flip(ind, bit):
    bit &= (1 << 19) - (1 << ind)
    return bitcnt[bit]

for i in range(1 << n):
    if i > 0:
        bitcnt[i] = bitcnt[i//2] + i%2
    for last in range(n):
        if i == (1<<n)-1:
            ans = min(ans, dp[i][last])
        if dp[i][last] == INF:
            continue
        if (not (i == 0 and last == 0)) and ((1 << last) & i) == 0:
            continue
        for nxt in range(n):
            if (1 << nxt) & i:
                continue
            if i != 0 and value(last, bitcnt[i]-1) > value(nxt, bitcnt[i]):
                continue
            nxtbit = i + (1 << nxt)
            dp[nxtbit][nxt] = min(dp[nxtbit][nxt], dp[i][last] + flip(nxt, i))
    

if ans == INF:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import itertools
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
def invnum(n,a):
    bit=Bit(n)
    res=0
    for j in range(n):
        res+=j-bit.sum(a[j])
        bit.add(a[j],1)
    return res
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
flag=0
M=-1
if N%2==0:
    M=N//2
else:
    M=N//2+1
ans=(N*(N-1))//2
for seq in itertools.combinations(range(N),M):
    X=[]
    Y=[]
    era=[0 for i in range(N)]
    for i in seq:
        if i%2==0:
            X.append((A[i],i))
        else:
            X.append((B[i],i))
        era[i]=1
    for i in range(N):
        if era[i]==0:
            if i%2==0:
                Y.append((B[i],i))
            else:
                Y.append((A[i],i))
    X.sort()
    Y.sort()
    L=[]
    if N%2==1:
        for i in range(M-1):
            L.append(X[i])
            L.append(Y[i])
        L.append(X[-1])
    else:
        for i in range(M):
            L.append(X[i])
            L.append(Y[i])
    #print(L)
    flag2=1
    for i in range(N-1):
        if L[i][0]>L[i+1][0]:
            flag2=0
            break
    if flag2==1:
        flag=1
        S=[L[i][1]+1 for i in range(N)]
        tmp=invnum(N,S)
        ans=min(tmp,ans)
if flag==1:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
def invnum(n,a):
    bit=Bit(n)
    res=0
    for j in range(n):
        res+=j-bit.sum(a[j])
        bit.add(a[j],1)
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
flag=0
M=-1
if N%2==0:
    M=N//2
else:
    M=N//2+1
ans=(N*(N-1))//2
for seq in itertools.combinations(range(N),M):
    X=[]
    Y=[]
    era=[0 for i in range(N)]
    for i in seq:
        if i%2==0:
            X.append((A[i],i))
        else:
            X.append((B[i],i))
        era[i]=1
    for i in range(N):
        if era[i]==0:
            if i%2==0:
                Y.append((B[i],i))
            else:
                Y.append((A[i],i))
    X.sort()
    Y.sort()
    L=[]
    if N%2==1:
        for i in range(M-1):
            L.append(X[i])
            L.append(Y[i])
        L.append(X[-1])
    else:
        for i in range(M):
            L.append(X[i])
            L.append(Y[i])
    #print(L)
    flag2=1
    for i in range(N-1):
        if L[i][0]>L[i+1][0]:
            flag2=0
            break
    if flag2==1:
        flag=1
        S=[L[i][1] for i in range(N)]
        tmp=0
        for i in range(N):
            for j in range(i+1,N):
                if S[i]>S[j]:
                    tmp+=1
        ans=min(tmp,ans)
if flag==1:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())


def solve():
    n = I()
    a = LI()
    b = LI()
    N = 2*n
    v = [[] for i in range(N)]
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if i&1 != j&1:
                if a[i] <= a[j]:
                    v[i].append(j)
                if b[i] <= b[j]:
                    v[i+n].append(j+n)
            else:
                if a[i] <= b[j]:
                    v[i].append(j+n)
                if b[i] <= a[j]:
                    v[i+n].append(j)
    B = 1<<n
    dp = [[float("inf")]*N for i in range(B)]
    for i in range(N):
        if i < n and i&1:
            continue
        if i >= n and not (i+n)&1:
            continue
        j = i if i < n else i-n
        dp[1<<j][i] = 0
    bitcount = [bin(i).count("1") for i in range(B)]
    for b in range(B):
        for i in range(N):
            bi = 1<<(i if i < n else i-n)
            if not b&bi:
                continue
            for j in v[i]:
                bj = 1<<(j if j < n else j-n)
                if b&bj:
                    continue
                nb = b|bj
                count = bitcount[b&(~(bj-1))]
                nd = dp[b][i]+count
                if nd < dp[nb][j]:
                    dp[nb][j] = nd
    ans = min(dp[-1])
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def sortable(m, A, B):
    if len(A) == 2:
        if m <= A[0] <= A[1]:
            return 0
        elif m <= B[1] <= B[0]:
            return 1
        return -1
    t = 10**9
    for i in range(len(A)):
        n = A[i] if i % 2 == 0 else B[i]
        if n < m:
            continue
        x = sortable(n, B[0:i] + A[i + 1:], A[0:i] + B[i + 1:])
        if x >= 0:
            t = min(t, x + i)
            if t <= i:
                break
    if t != 10 ** 9:
        return t
    return -1


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    if len(A) == 1:
        print(0)
    else:
        print(sortable(0, A, B))

main()