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 sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]

all_cards = []
for i, (aa, bb) in enumerate(zip(a, b)):
    all_cards.append((aa, bb, i))

def check(cards):
    pre = -1
    for c in cards:
        print(c)
        if c[0] >= pre:
            pre = c[0]
        else:
            return False
    else:
        return True

def cnt(l):
    ret = 0
    for i in range(len(l)-1):
        for j in range(i+1, len(l)):
            if l[i] > l[j]:
                ret += 1
    return ret

dic = {}
def dp(all_cards, l, p):
    i = len(l) + 1
    if len(l) == n:
        return cnt(l)
    ret = float('inf')
    for card in all_cards:
        if card[2] in l:
            continue
        if card[(i-(card[2]+1))%2] >= p:
            ret = min(ret, dp(all_cards, l+[card[2]], card[(i-(card[2]+1))%2]))
    dic[tuple(l)] = ret
    return ret

ans = dp(all_cards, [], -float('inf'))
if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]

all_cards = []
for i, (aa, bb) in enumerate(zip(a, b)):
    all_cards.append((aa, bb, i))

def check(cards):
    pre = -1
    for c in cards:
        print(c)
        if c[0] >= pre:
            pre = c[0]
        else:
            return False
    else:
        return True

def cnt(l):
    ret = 0
    for i in range(len(l)-1):
        for j in range(i+1, len(l)):
            if l[i] > l[j]:
                ret += 1
    return ret

def dp(all_cards, l, p):
    i = len(l) + 1
    if len(l) == n:
        return cnt(l)
    ret = float('inf')
    for card in all_cards:
        if card[2] in l:
            continue
        if card[(i-(card[2]+1))%2] >= p:
            ret = min(ret, dp(all_cards, l+[card[2]], card[(i-(card[2]+1))%2]))
    return ret

ans = dp(all_cards, [], -float('inf'))
if ans == float('inf'):
    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()))

INF = 1 << 29

"""
・dp[bit][s]
ビットに1が立っているカードはソートされて左から並んでいる。
そのとき最後の値をsにするのに必要な最小操作回数


"""
# 1 <= A,B <= 50, bitの立ち方が 0...0 ~ 1...1 の2**N
dp = [[INF for _ in range(50 + 1)] for _ in range((1 << N))]
# 0枚選んでいて右端が0は何もしてないのでコスト0
dp[0][0] = 0

for bit in range(1 << N):
    # 現在見ているbit列にいくつ1が立っているか＝カードを何枚既に選んで並べているか
    num_used = bin(bit).count("1")
    
    # bitで１が立っていない＝まだ使われていないカードがどこにあるか
    idx = num_used
    remaining = []
    for i in range(N):
        if not (bit & (1 << i)):
            # 一つ目が初期位置、二つ目は、bitで１が立っているやつらを左に寄せた時にどの位置にいるか
            remaining.append((i, idx))
            idx += 1

    for s in range(51):
        # bitの集合かつ、その右端にsの状態が作れないならスキップ
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            """
            ini  : initial position
            curr : current position
            現時点でnum_used-1のインデックスまでカードがソートされて並んでいる
            最初iniの位置にあったカードを最後尾に並べることを考える
            """
            num = A[ini] if abs(ini - num_used) % 2 == 0 else B[ini]

            """
            numが並んでるカードの最後尾より大きければ最後尾につける
            """
            if num >= s:
                # 元の集合と、iniの位置だけ１が立ってるものの論理和で、追加した状態を表す
                # その場合の最小コストは、既に求まっているもの or 新たにnum_usedの位置にiniのカードをあてたとき　の小さいほう
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))



# 全てのbitに1が立っている（全て並べ切った）時の最小コストが答え
ans = min(dp[-1][s] for s in range(51))

print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:


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

INF = float("inf")

"""
・dp[bit][s]
ビットに1が立っているカードはソートされて左から並んでいる。
そのとき最後の値をsにするのに必要な最小操作回数


"""
# 1 <= A,B <= 50, bitの立ち方が 0...0 ~ 1...1 の2**N
dp = [[INF for _ in range(50 + 1)] for _ in range((1 << N))]
# 0枚選んでいて右端が0は何もしてないのでコスト0
dp[0][0] = 0

for bit in range(1 << N):
    # 現在見ているbit列にいくつ1が立っているか＝カードを何枚既に選んで並べているか
    num_used = bin(bit).count("1")
    
    # bitで１が立っていない＝まだ使われていないカードがどこにあるか
    idx = num_used
    remaining = []
    for i in range(N):
        if not (bit & (1 << i)):
            # 一つ目が初期位置、二つ目は、bitで１が立っているやつらを左に寄せた時にどの位置にいるか
            remaining.append((i, idx))
            idx += 1

    for s in range(51):
        # bitの集合かつ、その右端にsの状態が作れないならスキップ
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            """
            ini  : initial position
            curr : current position
            現時点でnum_used-1のインデックスまでカードがソートされて並んでいる
            最初iniの位置にあったカードを最後尾に並べることを考える
            """
            num = A[ini] if abs(ini - num_used) % 2 == 0 else B[ini]

            """
            numが並んでるカードの最後尾より大きければ最後尾につける
            """
            if num >= s:
                # 元の集合と、iniの位置だけ１が立ってるものの論理和で、追加した状態を表す
                # その場合の最小コストは、既に求まっているもの or 新たにnum_usedの位置にiniのカードをあてたとき　の小さいほう
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))



# 全てのbitに1が立っている（全て並べ切った）時の最小コストが答え
ans = min(dp[-1][s] for s in range(51))

print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:


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

INF = float("inf")

"""
・dp[bit][s]
ビットに1が立っているカードはソートされて左から並んでいる。
そのとき最後の値をsにするのに必要な最小操作回数


"""
# 1 <= A,B <= 50, bitの立ち方が 0...0 ~ 1...1 の2**N
dp = [[INF for _ in range(50 + 1)] for _ in range((1 << N))]
# 0枚選んでいて右端が0は何もしてないのでコスト0
dp[0][0] = 0

for bit in range(1 << N):
    # 現在見ているbit列にいくつ1が立っているか＝カードを何枚既に選んで並べているか
    num_used = bin(bit).count("1")
    
    # bitで１が立っていない＝まだ使われていないカードがどこにあるか
    idx = num_used
    remaining = []
    for i in range(N):
        if not (bit & (1 << i)):
            # 一つ目が初期位置、二つ目は、bitで１が立っているやつらを左に寄せた時にどの位置にいるか
            remaining.append((i, idx))
            idx += 1

    for s in range(51):
        # bitの集合かつ、その右端にsの状態が作れないならスキップ
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            """
            ini  : initial position
            curr : current position
            現時点でnum_used-1のインデックスまでカードがソートされて並んでいる
            最初iniの位置にあったカードを最後尾に並べることを考える
            """
            num = A[ini] if abs(ini - num_used) % 2 == 0 else B[ini]

            """
            numが並んでるカードの最後尾より大きければ最後尾につける
            """
            if num >= s:
                # 元の集合と、iniの位置だけ１が立ってるものの論理和で、追加した状態を表す
                # その場合の最小コストは、既に求まっているもの or 新たにnum_usedの位置にiniのカードをあてたとき　の小さいほう
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))

ans = INF
for i in range(51):
    # 全てのbitに1が立っている（全て並べ切った）時の最小コストが答え
    ans = min(ans, dp[-1][i])

print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  # M:カードの数字の最大値+1
  M = max(max(A),max(B))+1
  INF=float('inf')
  # dp[mask][a]:maskのカードが操作済で、そのうち右端のカードの数字がaであるときの操作回数の最小値
  dp = [[INF for _ in range(M)] for _ in range(1<<N)]
  dp[0][0] = 0
  
  for i in range(1<<N):
    # idx:操作済カードの枚数
    idx = 0
    for k in range(N):
      #k番目のカードが操作済みかどうか判定する。iでk番目にフラグがたってたら、操作済みとする。
      if (i>>k)&1 == 1:
        idx += 1
    for j in range(M):
      if dp[i][j] >= INF:
        continue
      for k in range(N):
        # k:右端の操作済カードの次に来るカード
        # kがすでに操作済の場合はcontinueする
        
        # kが何回操作されるかによってkの数字が表の数字になるか裏の数字になるかが決まる
        if abs(k-idx)%2 == 0:
          c = A[k]
        else:
          c = B[k]
  
        # kの数字広義単調増加にならない場合はcontinue
        if j > c:
          continue
        
        # t:kを右端の操作済カードの次に並べるための操作回数
        # それは、初期配置でkより左にあってまだ操作済でないカードの枚数と一致する
        t = 0
        for l in range(k):
          if (i>>l)&1 == 0:
            t += 1
        #print(i,k,idx,c,dp[i|(1<<k)][c],t)
        dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+t)
  
  ans = INF
  for i in range(M):
    ans = min(dp[(1<<N)-1][i],ans)
  print(ans if ans < INF else -1)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ab=lambda i,j:a[i] if abs(i-j)%2==0 else b[i]
inf=10**9
dp=[n*[inf]for _ in range(2**n)]
dp[0][0]=0
for i in range(n):dp[2**i][i]=i
for bit in range(1,2**n):
  m=[0]*n
  ii=0
  for i in range(n):
    if bit&2**i:
      m[i]=ii
      ii+=1
  bit_count=ii
  for i in range(n):
    if bit&2**i==0:
      m[i]=ii
      ii+=1
  for i in range(n):
    if bit&2**i:continue
    ci=ab(i,bit_count)
    for j in range(n):
      if bit&2**j==0:continue
      cj=ab(j,bit_count-1)
      if cj>ci:continue
      dp[bit|2**i][i]=min(dp[bit|2**i][i],dp[bit][j]+m[i]-bit_count)
ans=inf
for i in range(n):ans=min(ans,dp[-1][i])
if ans==inf: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()))
# M:カードの数字の最大値+1
M = max(max(A),max(B))+1

INF = float('inf')
# dp[mask][a]:maskのカードが操作済で、そのうち右端のカードの数字がaであるときの操作回数の最小値
dp = [[INF for _ in range(M)] for _ in range(1<<N)]
dp[0][0] = 0

for i in range(1<<N):
  # idx:操作済カードの枚数
  idx = 0
  for k in range(N):
    if (i>>k)&1 == 1:
      idx += 1
  for j in range(M):
    if dp[i][j] >= INF:
      continue
    for k in range(N):
      # k:右端の操作済カードの次に来るカード
      # kがすでに操作済の場合はcontinueする
      if i&(1<<k) == 1:
        continue
      
      # kが何回操作されるかによってkの数字が表の数字になるか裏の数字になるかが決まる
      if abs(k-idx)%2 == 0:
        c = A[k]
      else:
        c = B[k]

      # kの数字広義単調増加にならない場合はcontinue
      if j > c:
        continue
      
      # t:kを右端の操作済カードの次に並べるための操作回数
      # それは、初期配置でkより左にあってまだ操作済でないカードの枚数と一致する
      t = 0
      for l in range(k):
        if (i>>l)&1 == 0:
          t += 1
      #print(i,k,idx,c,dp[i|(1<<k)][c],t)
      dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+t)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")


def bit_sum(n):
    return bin(n).count("1")


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

    DP = [[INF]*51 for _ in range(1 << N)]
    DP[0][0] = 0

    for bit in range(1 << N):

        ketawa = bit_sum(bit)

        # bit集合で表現されない値の位置を確認する
        rest = []
        counter = ketawa
        for i in range(N):
            if bit & (1 << i):
                continue
            rest.append((i, counter))
            counter += 1

        # 最後の数がsである場合から配るDP
        for s in range(51):
            if DP[bit][s] == INF:
                continue
            for orig, curr in rest:
                # 元の並びでorig番目にあったカードをketawa番目に移動する。
                # 表の値が確定する
                if (orig-ketawa) % 2 == 0:
                    front = A[orig]
                else:
                    front = B[orig]
                # 値がs以上なら、単調増加にできる
                if front >= s:
                    DP[bit | 1 << orig][front] = min(DP[bit | 1 << orig][front],
                                                     DP[bit][s]+abs(curr-ketawa))
    ans = min(DP[-1])
    if ans == INF:
        print(-1)
    else:
        print(ans)


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

Solution code:
#bit全探索


#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#Binary Indexed Tree (1-indexなので注意！！！！！！！！)
class BinaryIndexedTree():
    def __init__(self, size):
        self.__node=[0]*(size+1)
        self.size = size

    #node[index]にvalueを足して、BITを更新
    def add(self, index, value):
        while index <= self.size:
            self.__node[index] += value
            index += index&-index    
    
    #indexまでの和を返す
    def sum(self, index):
        ret = 0 #零元・単位元
        while index > 0:
            ret += self.__node[index]
            index -= index&-index    
        return ret

    def update_max(self, index, value):
        while index <= self.size:
            self.__node[index] = max(self.__node[index], value)
            index += index & -index


    #indexまでの最大値を返す
    def query_max(self, index):
        ret = 0
        while index > 0:
            ret = max(ret, self.__node[index])
            index -= index & -index
        return ret
        
        

    #0-indexでの添字を受け取って、1-indexでの添字での値を返す
    def get_node(self, index):
        return self.__node[index]
def Inversion_number(A):
    N=len(A)
    B=sorted(set(A))
    BIT = BinaryIndexedTree(N)
    res = 0
    for i in range(N):
        idx = bisect_left(B,A[i])
        inverse = i - BIT.sum(idx+1)
        res += inverse
        BIT.add(idx+1,1)
    return res

def main():
    N=I()
    A=LI()
    B=LI()
    max_bit = 1<<N


        
    def check(mask): 
        """
        ビットが立ってるところは裏
        裏になるものは元いる位置から奇数移動
        表になるものは元いる位置から偶数移動
        """
        C=[0]*N
        for i in range(N):
            if (mask>>i&1):
                C[i] = (B[i],i)
            else:
                C[i] = (A[i],i)

        C.sort()
        dic = defaultdict(lambda : deque())
        for j,(c,i) in enumerate(C):
            dic[c,j&1].append(j)
        
        indexes = [0]*N
        for i in range(N):
            if (mask>>i&1):
                num,is_odd_idx = (B[i],i&1)
                if dic[num,is_odd_idx^1]:
                    idx = dic[num,is_odd_idx^1].popleft()
                else:
                    return inf
            else:
                num,is_odd_idx = A[i],i&1
                if dic[num,is_odd_idx]:
                    idx = dic[num,is_odd_idx].popleft()
                else:
                    return inf
            indexes[i] = idx

        return Inversion_number(indexes)


    ans = inf
    for mask in range(max_bit):
        res = check(mask)
        if res < ans:
            ans = res
    if ans == inf:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#bit全探索


#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#Binary Indexed Tree (1-indexなので注意！！！！！！！！)
class BinaryIndexedTree():
    def __init__(self, size):
        self.__node=[0]*(size+1)
        self.size = size

    #node[index]にvalueを足して、BITを更新
    def add(self, index, value):
        while index <= self.size:
            self.__node[index] += value
            index += index&-index    
    
    #indexまでの和を返す
    def sum(self, index):
        ret = 0 #零元・単位元
        while index > 0:
            ret += self.__node[index]
            index -= index&-index    
        return ret

    def update_max(self, index, value):
        while index <= self.size:
            self.__node[index] = max(self.__node[index], value)
            index += index & -index


    #indexまでの最大値を返す
    def query_max(self, index):
        ret = 0
        while index > 0:
            ret = max(ret, self.__node[index])
            index -= index & -index
        return ret
        
        

    #0-indexでの添字を受け取って、1-indexでの添字での値を返す
    def get_node(self, index):
        return self.__node[index]
def main():
    N=I()
    A=LI()
    B=LI()
    max_bit = 1<<N

    def Inversion_number(A):
        N=len(A)
        B=sorted(set(A))
        BIT = BinaryIndexedTree(N)
        res = 0
        for i in range(N):
            idx = bisect_left(B,A[i])
            inverse = i - BIT.sum(idx+1)
            res += inverse
            BIT.add(idx+1,1)
        return res

        
    def check(mask): 
        """
        ビットが立ってるところは裏
        裏になるものは元いる位置から奇数移動
        表になるものは元いる位置から偶数移動
        """
        C=[0]*N
        for i in range(N):
            if (mask>>i&1):
                C[i] = (B[i],i)
            else:
                C[i] = (A[i],i)

        C.sort()
        dic = defaultdict(lambda : deque())
        for j,(c,i) in enumerate(C):
            dic[c,j&1].append(j)
        
        indexes = []
        for i in range(N):
            if (mask>>i&1):
                num,is_odd_idx = (B[i],i&1)
                if dic[num,is_odd_idx^1]:
                    idx = dic[num,is_odd_idx^1].popleft()
                else:
                    return inf
            else:
                num,is_odd_idx = A[i],i&1
                if dic[num,is_odd_idx]:
                    idx = dic[num,is_odd_idx].popleft()
                else:
                    return inf
            indexes.append(idx)

        return Inversion_number(indexes)


    ans = inf
    for mask in range(max_bit):
        res = check(mask)
        if res < ans:
            ans = res
    if ans == inf:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/keyence2020/submissions/9568282

def main():
    from collections import namedtuple
    from itertools import accumulate, combinations

    inf = 1 << 29

    Card = namedtuple('Card', 'i_ a_ b_')  # 0-indexed
    Card.front = lambda self, i: self.a_ if (self.i_ - i) % 2 == 0 else self.b_  # 0-indexedでiに移動したときの表面の数値

    n = int(input())
    *a, = map(int, input().split())
    *b, = map(int, input().split())

    cards = [Card(i_=i_, a_=a_, b_=b_) for i_, (a_, b_) in enumerate(zip(a, b))]

    dp = [[inf] * (n + 1) for _ in range(1 << n)]
    dp[0][n] = 0
    # dp[bit][tail_idx]:=最小転倒数
    # bit: 0-indexed * n頂点
    # tail_idx: 0-indexed * n頂点, {0,1,...,n-1}, n=末尾なしに相当

    for already_set in range(n):
        for used in combinations(cards, r=already_set):
            not_used = set(cards).difference(used)
            bit_con = len(used)

            bit = sum(1 << card.i_ for card in used)
            inv = [(bit >> j) & 1 for j in range(n)]
            for i in range(n - 2, -1, -1):
                inv[i] += inv[i + 1]
            # inv[not_used_card.i_]
            # [0,1,...,n-1]の順序のとき
            # not_used_card.i_よりも右にあったカードで、usedの数
            # usedのため、今はnot_used_card.i_よりも左にあって、転倒数の計上にかかわる

            if not used:
                used = {Card(i_=n, a_=-inf, b_=-inf)}  # 番兵

            for prev_card in used:
                prev_val = prev_card.front(bit_con - 1)
                for new_card in not_used:
                    new_val = new_card.front(bit_con)
                    new_bit = bit | (1 << new_card.i_)
                    if prev_val <= new_val:
                        dp[new_bit][new_card.i_] = min(
                            dp[new_bit][new_card.i_],
                            dp[bit][prev_card.i_] + inv[new_card.i_]
                        )

    ans = inf
    for tail_idx in range(n):
        ans = min(ans, dp[(1 << n) - 1][tail_idx])

    print(-1 if ans == inf else ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
import itertools
c=set()
for i in range(n):
  if i%2:c.add((b[i],a[i],i))
  else:c.add((a[i],b[i],i))
ans=inf=float('inf')
for i in itertools.combinations(c,(n+1)//2):
  ii=c-set(i)
  ac=[(j[0],j[2])for j in i]
  bc=[(j[1],j[2])for j in ii]
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
import itertools
c=[]
for i in range(n):
  if i%2:c.append((b[i],a[i],i))
  else:c.append((a[i],b[i],i))
ans=inf=float('inf')
for i in itertools.combinations(c,(n+1)//2):
  s=set(i)
  ac=[]
  bc=[]
  for j in c:
    if j in s:ac.append((j[0],j[2]))
    else:bc.append((j[1],j[2]))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
import itertools
xx=[i for i in range(n)]
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in itertools.combinations(xx,(n+1)//2):
  s=set(i)
  ac=[]
  bc=[]
  for j in range(n):
    if j in s:ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  m=[]
  for j in range(n):
    if j%2:
      x.append(bc[j//2][0])
      m.append(bc[j//2][1])
    else:
      x.append(ac[j//2][0])
      m.append(ac[j//2][1])
  f=False
  for j in range(1,n):
    if x[j-1]>x[j]:f=True
  if f:continue
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
import itertools
xx=[i for i in range(n)]
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in itertools.combinations(xx,(n+1)//2):
  s=set(i)
  ac=[]
  bc=[]
  for j in range(n):
    if j in s:ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  m=[]
  for j in range(n):
    if j%2:
      x.append(bc[j//2][0])
      m.append(bc[j//2][1])
    else:
      x.append(ac[j//2][0])
      m.append(ac[j//2][1])
  f=False
  for j in range(1,n):
    if x[j-1]>x[j]:f=True
  if f:continue
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
import itertools
xx=[i for i in range(n)]
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in itertools.combinations(xx,(n+1)//2):
  s=set(i)
  ac=[]
  bc=[]
  for j in range(n):
    if j in s:ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)