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: Accepted

Solution code:
# from collections import defaultdict,deque
# import sys,heapq,bisect,math,itertools,string,queue,copy,time
# sys.setrecursionlimit(10**8)
#
#
import sys
import itertools
INF = float("INF")

N = int(input())
AA = list(map(int, sys.stdin.readline().split()))
BB = list(map(int, sys.stdin.readline().split()))

cards = set()
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.add((a, b, i))
    else:
        cards.add((b, a, i))

def solve(ii):
    tmp = 0
    for i in range(N):
        for j in range(i+1,N):
            if ii[i] > ii[j]:
                tmp += 1
    return tmp

ans = INF
for Acards in itertools.combinations(cards, (N+1)//2):
    Bcards = cards - set(Acards)

    Ais = sorted([(card[0], card[2]) for card in Acards])
    Bis = sorted([(card[1], card[2]) for card in Bcards])

    bn = -1
    ii = []
    flag = False
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        if bn > n:
            flag = True
        bn = n
        ii.append(i)

    if flag: continue

    ans = min(ans,solve(ii))


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

Submission status: Accepted

Solution code:
# from collections import defaultdict,deque
# import sys,heapq,bisect,math,itertools,string,queue,copy,time
# sys.setrecursionlimit(10**8)
#
#
import sys
import itertools
INF = float("INF")

N = int(input())
AA = list(map(int, sys.stdin.readline().split()))
BB = list(map(int, sys.stdin.readline().split()))

cards = set()
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.add((a, b, i))
    else:
        cards.add((b, a, i))




# In[]:
def solve(ii):
    tmp = 0
    for _ in range(N):
        next = []
        for k, i in enumerate(ii):
            if i == 0:
                tmp += k
            else:
                next.append(i-1)
        ii = next[:]
    return tmp



# In[]:
ans = INF
for Acards in itertools.combinations(cards, (N+1)//2):
    Bcards = cards - set(Acards)

    Ais = sorted([(card[0], card[2]) for card in Acards])
    Bis = sorted([(card[1], card[2]) for card in Bcards])

    nums = []
    ii = []
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        nums.append(n)
        ii.append(i)

    if nums != sorted(nums):
        continue
    else:
        ans = min(ans,solve(ii))
        if ans == 0:
          print(0)
          sys.exit()


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

Submission status: Accepted

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

INF = 1 << 29
dp = [[INF] * 55 for _ in range((1 << N) + 1)]
dp[0][0] = 0

for bit in range(1 << N):
    con = 0
    for i in range(N):
        if bit & (1 << i):
            con += 1
            
    ords = []
    iters = con
    for i in range(N):
        if not (bit & (1 << i)):
            ords.append([i, iters])
            iters += 1

    for s in range(51):
        if dp[bit][s] >= INF:
            continue

        for p in ords:
            # p[0]: 元々のaのindex, p[1]: dp[bit][s]の状態でのindex
            ns = -1
            if abs(p[0] - con) % 2 == 0:
                ns = A[p[0]]
            else:
                ns = B[p[0]]

            if ns >= s:
                dp[bit|(1 << p[0])][ns] = min(dp[bit|(1 << p[0])][ns],
                                              dp[bit][s] + abs(p[1] - con))
                    
ans = INF
for s in range(51):
    ans = min(ans, dp[(1 << N) - 1][s])
if ans < INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

#インデックス付きソート
#(index,value)の順に格納
from operator import itemgetter
def index_sort(A):
    return sorted(enumerate(A),key=itemgetter(1))

ceil = math.ceil
floor = math.floor

N = I()
A = III()
B = III()

ans = float('inf')
for i in range(1<<N):
    bits = format(i,'b').zfill(N)
    last_odd_val = []
    last_even_val = []
    for j,b in enumerate(bits):
        if j%2==0:
            if b=='0':
                last_even_val.append([A[j],j])
            else:
                last_odd_val.append([B[j],j])
        else:
            if b=='0':
                last_odd_val.append([A[j],j])
            else:
                last_even_val.append([B[j],j])

    if len(last_even_val)!=ceil(N/2):
        continue

    s_odd = sorted(last_odd_val,key=lambda x:(x[0],x[1]))
    s_even = sorted(last_even_val,key=lambda x:(x[0],x[1]))
    flag = False
    eps = 10**(-2)
    for j in range(N//2):
        if floor(s_even[j][0])>floor(s_odd[j][0]):
            flag = True
            break
        if floor(s_even[j][0])==floor(s_odd[j][0]):
            s_odd[j][0] = s_even[j][0] + eps
        if len(s_even)>j+1:
            if floor(s_odd[j][0])>floor(s_even[j+1][0]):
                flag = True
                break
            if floor(s_odd[j][0])==floor(s_even[j+1][0]):
                s_even[j+1][0] = s_odd[j][0] + eps

    if flag:
        continue

    val = [0.0]*N
    for s in s_even:
        val[s[1]] = s[0]
    for s in s_odd:
        val[s[1]] = s[0]

    count = 0
    for i in range(N):
        for j in range(i+1,N):
            if val[i]>val[j]:
                count += 1
    
    if count<ans:
        ans = count

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

Submission status: Accepted

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

#0-indexed

#カードiが左からjの位置にあるときの表の数字
def getNum(i,j):
    return B[i] if abs(i-j)&1 else A[i]

#dp[使用済みカードを表すbit列][いちばん右のカードNo]=最小操作回数
INF=10**9
dp=[[INF for _ in range(N)] for __ in range(1<<N)]
for i in range(N):
    dp[1<<i][i] = i

for m in range(1,1<<N): #配置済みカードパターン
    cnt=bin(m).count('1') #配置済みカード数
    idx=dict() #未配置カードの位置
    tmp=cnt
    for i in range(N):
        if m & (1<<i) == 0:
            idx[i]=tmp
            tmp+=1
    for j in range(N): #新たに並べるカード
        if m & (1<<j):
            #もう使ったやつです
            continue
        num_j=getNum(j,cnt)
        for i in range(N): #配置済みのいちばん右にあるカード
            if m & (1<<i) == 0:
                #まだ配置済みじゃないです
                continue
            num_i=getNum(i,cnt-1)
            if num_i>num_j:
                #単調増加になりません
                continue
            dp[m|(1<<j)][j] = min(dp[m|(1<<j)][j], dp[m][i] + idx[j]-cnt)

ans=INF
for i in range(N):
    ans=min(ans,dp[(1<<N)-1][i])
print(ans if ans<INF else -1)

Submission status: Accepted

Solution code:

from collections import defaultdict
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 tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += i-bit.sum(p)
        bit.add(p, 1)
    return ans
N = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
us = []
vs = []
for i in range(N):
    a, b = xs[i], ys[i]
    if i%2:
        us.append((a,i))
        vs.append((b,i))
    else:
        us.append((b,i))
        vs.append((a,i))
vs.sort()
r = 10**18
for i in range(2**N):
    t = 0
    tt = 0
    rs = [0]*N
    rs2 = [0]*(N//2)
    for j in range(N):
        if i%2:
            if 2*t < N:
                rs[t*2] = vs[j]
            t += 1
        else:
            if 2*tt+1 < N:
                rs2[tt] = us[vs[j][1]]
            tt += 1
        i = i>>1
    if t != (N+1)//2:
        continue
    rs2.sort()
    for i in range(N//2):
        rs[i*2+1] = rs2[i]
    b,ff = 0,0
    for z,j in rs:
        if b>z:
            ff = 1
            break
        b = z
    if ff:
        continue
#    print(rs)
    rs = [j+1 for _,j in rs]
    r = min(r, tento(rs))
print(r if r != 10**18 else -1)

Submission status: Accepted

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

def solve(N: int, A: "List[int]", B: "List[int]"):
    answer = 10**10
 
    ## 奇数indexにくるものを決め打ち
    for c in combinations(range(N), N//2):
        even, odd= [], []
        
        for i in range(N):
            if i in c:
                odd.append((A[i] if i % 2 == 1 else B[i],i))
            else:
                even.append((A[i] if i % 2 == 0 else B[i],i))
    
        even.sort()
        odd.sort()
        t = []
        ind = []
        
        for i in range(N//2):
            t.append(even[i][0])
            t.append(odd[i][0])
            ind.append(even[i][1])
            ind.append(odd[i][1])
        else:
            if N%2 == 1:
                t.append(even[-1][0])
                ind.append(even[-1][1])
        
        if t != sorted(t):
            continue

        tentousuu = 0
        for i in range(N-1):
            for j in range(i+1,N):
                if ind[i] > ind[j]:
                    tentousuu += 1
        
        if answer > tentousuu:
            answer = tentousuu

    if answer == 10**10:
        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: Accepted

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

def solve(N: int, A: "List[int]", B: "List[int]"):
    answer = 10**18
 
    ## 奇数indexにくるものを決め打ち
    for c in combinations(range(N), N//2):
        even, odd= [], []
        
        for i in range(N):
            if i in c:
                odd.append((A[i] if i % 2 == 1 else B[i],i))
            else:
                even.append((A[i] if i % 2 == 0 else B[i],i))
    
        even.sort()
        odd.sort()
        t = []
        ind = []
        
        for i in range(N//2):
            t.append(even[i][0])
            t.append(odd[i][0])
            ind.append(even[i][1])
            ind.append(odd[i][1])

        if N%2 == 1:
            t.append(even[-1][0])
            ind.append(even[-1][1])
        
        if t != sorted(t):
            continue

        tentousuu = 0
        for i in range(N-1):
            for j in range(i+1,N):
                if ind[i] > ind[j]:
                    tentousuu += 1
        
        answer = min(answer,tentousuu)


    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: Accepted

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
    if n == 1:
        print(0)
        return
    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: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]

odd_bit = 0b0101010101010101010101
eve_bit = 0b1010101010101010101010
full_bit = 2**n - 1

odd_num = (n + 1) // 2
ans = 10**9 

for i in range(2**n):
    invi = full_bit ^ i
    odd = bin(i & odd_bit).count("1") + bin(invi & eve_bit).count("1")
    if odd != odd_num:
        continue
    odd_card = []
    eve_card = []
    for j in range(n):
        if i & 1 << j:
            if j % 2 == 0:
                odd_card.append((a[j], j))
            else:
                eve_card.append((a[j], j))
        else:
            if j % 2 == 0:
                eve_card.append((b[j], j))
            else:
                odd_card.append((b[j], j))
    odd_card.sort()
    eve_card.sort()
    odd_itr = 0
    eve_itr = 0
    curr = 0
    val = 0
    ok = True
    perm = []
    for i in range(n):
        if i % 2 == 0:
            num, index = odd_card[odd_itr]
            perm.append(index)
            odd_itr += 1
        else:
            num, index = eve_card[eve_itr]
            perm.append(index)
            eve_itr += 1
        if num < curr:
            ok = False
            break
        curr = num
    if ok:
        val = 0
        visited = [0] * n
        itr = 0
        for item in perm:
            visited[item] = 1
            val += itr - sum(visited[:item])
            itr += 1
        ans = min(ans, val)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n =int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]

L = range(n)
from itertools import combinations

ans = INF = 1000000
for I in combinations(L,n//2): #偶数番目を決め打ち全探索
    even = [(a[i] if i%2 else b[i], i) for i in I]
    odd  = [(b[i] if i%2 else a[i], i) for i in range(n) if i not in I]
    
    odd.sort()
    even.sort()
    ok = 1
    #偶数番目と奇数番目をマージしたとき、ソートされているか確認
    for i in range(n//2):
        if odd[i][0] > even[i][0]:
            ok = 0
            break
    for i in range(1,n-n//2):
        if even[i-1][0] > odd[i][0]:
            ok = 0
            break
    
    if ok:
        res = [0]*n
        for i in range(n//2):
            res[2*i+1] = even[i][1]
        for i in range(n-n//2):
            res[2*i] = odd[i][1]
        
        #転倒数の計算
        cnt = 0        
        for i in range(n):
            for j in range(i+1,n):
                if res[i] > res[j]: cnt += 1
        ans = min(ans,cnt)


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

Submission status: Accepted

Solution code:
import itertools
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

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:
      ten=0
      for i1 in range(n):
        for i2 in range(i1+1,n):
          if C[i1]>C[i2]:
            ten+=1
      ans=min(ans,ten)
print(-1 if ans==float("inf") else ans)

Submission status: Accepted

Solution code:

N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = float("inf")

for loop in range(2 ** N):

    s = format(loop,'b').zfill(N) #sはどのカードが奇数番目かを表す。ビットの組み合わせを2^N通り入れて全探索。
    on = 0
    
    for j in s:
        if j == "1":
            on += 1

    if on != (N+1)//2: #sの立っているビットの数が奇数番目の位置の個数に合っていなかったら飛ばす
        continue

    q = []  #奇数番目に置くカードの集合
    q2 = [] #偶数番目に置くカードの集合

    for i in range(N): #カードの位置の偶奇に合わせて表裏を決める
        if s[i] == "1":
            if i % 2 == 0:
                q.append([A[i],i])
            else:
                q.append([B[i],i])
        else:
            if i % 2 != 0:
                q2.append([A[i],i])
            else:
                q2.append([B[i],i])           

    q.sort()
    q2.sort()
    q2.append([float("inf"),0]) #偶数番目は1枚少ないことがあるので番兵
    

    flag = True #昇順になっているかのフラグ
    nmax = 0    #現在の最大値(昇順判定に使う)

    for i in range((N+1)//2): #昇順判定プロセス


        if nmax > q[i][0]:
            flag = False
        nmax = q[i][0]

        if nmax > q2[i][0]:
            flag = False
        nmax = q2[i][0]

    if flag: #昇順だったらrにカードの番号(not 書かれている数字)を入れてく
        r = []
        for i in range((N+1)//2):
            r.append(q[i][1])
            r.append(q2[i][1])

        #ここから転倒数の計算(無理やりシミュレーション)
        now = 0
        z = [i for i in range(N)]
        for i in range(N):
            for j in range(len(z)):
                if z[j] == r[i]:
                    now += j
                    del z[j]
                    break
        ans = min(now,ans) #求める答えは転倒数の最小値

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

Submission status: Accepted

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<=64:
    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: Accepted

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 t[j]>t[i]: tans+=1
        ans=min(ans,tans)

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

Submission status: Accepted

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
    for i in range(n):
        for j in range(i,n):
            if l[i]>l[j]:
                cnt += 1
    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):
    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()
    if n%2:
        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
    else:
        for i in range(n//2):
            if i != n//2-1:
                if odd_li[i][0] <= even_li[i][0] <= odd_li[i+1][0]:
                    continue
                else:
                    f = False; break
            else:
                if odd_li[-1][0] <= even_li[-1][0]:
                    continue
                else:
                    f = False; break
    if f:
        after_ind = []
        for i in range(n//2):
            after_ind.append(odd_li[i][1])
            after_ind.append(even_li[i][1])
        if n%2:
            after_ind.append(odd_li[-1][1])
        res = min(res,swap(after_ind))
print(-1 if res == INF else res)

Submission status: Accepted

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[1]) != 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: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]

def chk(L):
    NN = 5
    BIT=[0] * (2**NN+1)
    def addbit(i):
        while i <= 2**NN:
            BIT[i] += 1
            i += i & (-i)
 
    def getsum(i):
        ret = 0
        while i != 0:
            ret += BIT[i]
            i -= i&(-i)
        return ret
    s = 0
    for l in L[::-1]:
        s += getsum(l+1)
        addbit(l+1)
    return s
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: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N = inp()
AA = inpl()
BB = inpl()

# In[]:
# N = 3
# AA = [3, 4, 3]
# BB = [3, 2, 3]

cards = []
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.append((a, b, i))
    else:
        cards.append((b, a, i))


n = (N+1)//2

# In[]:
def solve(ii):
    tmp = 0
    # print(ii)
    for _ in range(N):
        next = []
        for k, i in enumerate(ii):
            if i == 0:
                tmp += k
            else:
                next.append(i-1)
        ii = next[:]
    # print(tmp)
    return tmp



# In[]:
ans = INF
for Acards in itertools.combinations(cards, n):
    Ais = sorted([(Acard[0], Acard[2]) for Acard in Acards])

    ii = set([i for A,i in Ais])
    Bis = []
    for a,b,i in cards:
        if i not in ii:
            Bis.append((b,i))
    Bis.sort()

    nums = []
    ii = []
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        nums.append(n)
        ii.append(i)

    # print(nums,ii)
    if nums != sorted(nums):
        continue
    else:
        ans = min(ans,solve(ii))
        if ans == 0:
          print(0)
          sys.exit()


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

Submission status: Accepted

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]
def chk(L):
    NN = 5
    BIT=[0] * (2**NN+1)
    def addbit(i):
        while i <= 2**NN:
            BIT[i] += 1
            i += i & (-i)
 
    def getsum(i):
        ret = 0
        while i != 0:
            ret += BIT[i]
            i -= i&(-i)
        return ret
    s = 0
    for l in L[::-1]:
        s += getsum(l+1)
        addbit(l+1)
    return s
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)