Problem:


Score : 700 points

Problem Statement

We have N cards numbered 1, 2, ..., N.
Card i (1 \leq i \leq N) has an integer A_i written in red ink on one side and an integer B_i written in blue ink on the other side.
Initially, these cards are arranged from left to right in the order from Card 1 to Card N, with the red numbers facing up.

Determine whether it is possible to have a non-decreasing sequence facing up from left to right (that is, for each i (1 \leq i \leq N - 1), the integer facing up on the (i+1)-th card from the left is not less than the integer facing up on the i-th card from the left) by repeating the operation below. If the answer is yes, find the minimum number of operations required to achieve it.

Choose an integer i (1 \leq i \leq N - 1).
Swap the i-th and (i+1)-th cards from the left, then flip these two cards.

Constraints

1 \leq N \leq 18

1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Output

If it is impossible to have a non-decreasing sequence, print -1.
If it is possible, print the minimum number of operations required to achieve it.

Sample Input 1

3
3 4 3
3 2 3

Sample Output 1

1

By doing the operation once with i = 1, we have a sequence [2, 3, 3] facing up, which is non-decreasing.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

After any number of operations, we have the sequence [2, 1] facing up, which is not non-decreasing.

Sample Input 3

4
1 2 3 4
5 6 7 8

Sample Output 3

0

No operation may be required.

Sample Input 4

5
28 15 22 43 31
20 22 43 33 32

Sample Output 4

-1

Sample Input 5

5
4 46 6 38 43
33 15 18 27 37

Sample Output 5

3



Sample input:
3
3 4 3
3 2 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
class BIT:
    #1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(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 bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1

def count(P):
    res = 0
    T = BIT(N)
    for i in range(N):
        p = P[i]
        res += i-T.get(p+1)
        T.add(p+1, 1)
    return res

N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
uhalf = -(-N//2)
dhalf = N - uhalf
inf = 10**10
ans = inf
for S in range(1<<N):
    card = [A[i] if S&(1<<i) else B[i] for i in range(N)]
    parity = [(1&(S>>i))^(i&1) for i in range(N)]
    even = [(card[i], i) for i in range(N) if parity[i]]
    odd = [(card[i], i) for i in range(N) if not parity[i]]
    if len(even) != uhalf or len(odd) != dhalf:
        continue
    even.sort()
    odd.sort()
    if any(e > o for e, o in zip(even, odd)) or any(e < o for e, o in zip(even[1:], odd)):
        continue
    perm = [even[i//2][1] if not i&1 else odd[i//2][1] for i in range(N)]
    '''
    print(perm)
    print(even)
    print(odd)
    '''
    ans = min(ans, count(perm))
print(ans if ans < inf else -1)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    for bit in range(1 << (N-1)):
        res = A[:]
        now = B[:]
        ans = 0
        flag = True
        for i in range(N - 1):
            if bit & (1 << i):
                ans += 1
                res[i], res[i+1], now[i], now[i+1] \
                    = now[i+1], now[i], res[i+1], res[i]
        for i in range(N-1):
            if res[i] > res[i+1]:
                flag = False
        if flag:
            return print(ans)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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(3):
        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 == INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = float("inf")
for i in range(2**n):
  L = []
  G = []
  for j in range(n):
    if i>>j & 1:
      L.append(B[j])
      G.append(1)
    else:
      L.append(A[j])
      G.append(0)
  C = [0]*n
  cnt = 0
  for s in range(n-1):
    for t in range(s+1, n):
      if L[s] > L[t]:
        C[s] ^= 1
        C[t] ^= 1
        cnt += 1
  if C == G:
    ans = min(ans, cnt)
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

ans = 10**9

for i in range(2 ** n):
    j = 1
    c = []
    count = 0
    for k in range(n):
        if (i&j)==0:
            c.append((a[k], k, 0))
        else:
            c.append((b[k], k, 1))
            count += 1
        j *= 2
    if count % 2 != 0:
        continue
    
    c.sort()
    gu = 0
    guw = 0
    flag = True
    cost = 0
    for j in range(n):
        t = c[j]
        cost += abs(t[1]-j)
        if (t[1] + t[2]) % 2 == 0:
            guw += 1
        if j % 2 == 0:
            gu += 1
        if j == n - 1 or c[j][0] != c[j + 1][0]:
            if gu != guw:
                flag = False
            gu = 0
            guw = 0
    if not flag:
        continue
    ans = min(cost // 2, ans)
if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

ans = 10**9

for i in range(2 ** n):
    j = 1
    c = []
    count = 0
    for k in range(n):
        if (i&j)==0:
            c.append((a[k], k, 0))
        else:
            c.append((b[k], k, 1))
            count += 1
        j *= 2
    if count % 2 != 0:
        continue
    
    c.sort()
    gu = 0
    guw = 0
    flag = True
    cost = 0
    for j in range(n):
        t = c[j]
        cost += abs(t[1]-j)
        if (t[1] + t[2]) % 2 == 0:
            guw += 1
        if j % 2 == 0:
            gu += 1
        if j == n - 1 or c[j][0] != c[j + 1][0]:
            if gu != guw:
                flag = False
            gu = 0
            guw = 0
    if not flag:
        continue
    ans = min(cost // 2, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
AB = (A, B)
INF = 10**18

ans = INF
for state in range(1 << N):
    even = []
    odd = []

    for i in range(N):
        isReverse = (state & (1 << i)) >> i
        val = AB[isReverse][i]

        if i % 2 == 0:
            (even, odd)[isReverse].append((val, i))
        else:
            (odd, even)[isReverse].append((val, i))

    if len(even) != -(-N // 2) or len(odd) != N // 2:
        continue

    even.sort()
    odd.sort()
    odd.append((-1, -1))
    V = []
    P = []
    for (l, i), (r, j) in zip(even, odd):
        V.append(l)
        P.append(i)
        if r >= 0:
            V.append(r)
            P.append(j)

    if not all(l <= r for l, r in zip(V, V[1:])):
        continue

    cnt = 0
    for i, p in enumerate(P):
        for q in P[:i]:
            if p < q:
                cnt += 1
    ans = min(ans, cnt)

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 = 10**18
AB = [A, B]

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

for state in range(1 << N):
    size = 0
    for i in range(N):
        if (state & (1 << i)) > 0:
            size += 1

    S = []
    now = size
    for i in range(N):
        if (state & (1 << i)) == 0:
            S.append((i, now))
            now += 1

    for s in range(51):
        for i, now in S:
            val = AB[(i - size) % 2][i]
            d = dp[state][s] + abs(now - size)
            if val >= s and dp[state | (1 << i)][val] > d:
                dp[state | (1 << i)][val] = d

ans = min(dp[(1 << N) - 1])
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 = 10**18
AB = [A, B]

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

for state in range(1 << N):
    size = 0
    for i in range(N):
        if (state & (1 << i)) > 0:
            size += 1

    S = []
    now = size
    for i in range(N):
        if (state & (1 << i)) == 0:
            S.append((i, now))
            now += 1

    for s in range(51):
        for i, now in S:
            val = AB[(i - size) % 2][i]
            if val >= s:
                dp[state | (1 << i)][val] = min(dp[state | (1 << i)][val], dp[state][s] + abs(now - size))

ans = min(dp[(1 << N) - 1])
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 = 10**18
AB = [A, B]

def calc(P):
    ret = 0
    for i, p in enumerate(P):
        for q in P[:i]:
            if q > p:
                ret += 1
    return ret

I = set()
def search(P, prev):
    i = len(P)

    if i == N:
        return calc(P)

    ret = INF

    for j in range(N):
        if j in I:
            continue
        n = AB[(i - j) % 2][j]
        if prev > n:
            continue
        P.append(j)
        I.add(j)
        ret = min(ret, search(P, n))
        I.remove(j)
        P.pop()

    return ret

ans = search([], -10**18)

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

Submission status: Time Limit Exceeded

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

import itertools
n = inn()
a = inl()
b = inl()
cms = itertools.combinations(list(range(n)),n//2)
mn = BIG
for cm in cms:
    ev = []
    od = []
    for i in range(n):
        if i not in cm:
            ev.append((a[i] if i%2==0 else b[i], i))
        else:
            od.append((a[i] if i%2==1 else b[i], i))
    ev.sort()
    od.sort()
    ddprint(f"{ev=}")
    ddprint(f"{od=}")
    p = []
    q = []
    for i in range(n):
        if i%2==0:
            p.append(ev[i//2][1])
            q.append(ev[i//2][0])
        else:
            p.append(od[i//2][1])
            q.append(od[i//2][0])
    ddprint(f"{cm=}")
    ddprint(f"{p=}")
    ddprint(f"{q=}")
    ok = True
    for i in range(n-1):
        if q[i]>q[i+1]:
            ok = False
            break
    if not ok:
        continue
    x = 0
    for i in range(n//2):
        ddprint(f"{i=}")
        m = p.index(i)
        tmp = p[m]
        for j in range(m,i,-1):
            p[j] = p[j-1]
        p[i] = tmp
        x += m-i
        ddprint(f"{m=} {p=}")
        m = p.index(n-1-i)
        tmp = p[m]
        for j in range(m,n-1-i):
            p[j] = p[j+1]
        p[n-1-i] = tmp
        x += n-1-i-m
        ddprint(f"{m=} {p=}")
    ddprint(f"{x=}")
    mn = min(mn,x)
print(mn if mn<BIG else -1)

Submission status: Time Limit Exceeded

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

used = [False] * N
def solve(index, cur_elem, cost, cur_min):
    #print(" " * index, cur_elem, cost, cur_min)
    for i in range(N):
        if used[i]:
            continue

        if (index - i) % 2 == 0:
            if A[i] >= cur_elem:
                new_cost = cost
                for j in range(i, N):
                    if used[j]:
                        new_cost += 1
                if new_cost < cur_min:
                    if index + 1 == N and new_cost < cur_min:
                        cur_min = new_cost
                    else:
                        used[i] = True
                        cur_min = min(cur_min, solve(index + 1, A[i], new_cost, cur_min))
                        used[i] = False
        else:
            if B[i] >= cur_elem:
                cost_delta = 0
                for j in range(i, N):
                    if used[j]:
                        cost_delta += 1
                new_cost = cost + cost_delta
                if new_cost < cur_min:
                    if index + 1 == N and new_cost < cur_min:
                        cur_min = new_cost
                    else:
                        used[i] = True
                        cur_min = min(cur_min, solve(index + 1, B[i], new_cost, cur_min))
                        used[i] = False
    return cur_min

ans = solve(0, -1, 0, 100000)
if ans == 100000:
    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()))

used = [False] * N
def solve(index, cur_elem, cost, cur_min):
    #print(" " * index, cur_elem, cost, cur_min)
    for i in range(N):
        if used[i]:
            continue

        if (index - i) % 2 == 0:
            if A[i] >= cur_elem:
                new_cost = cost
                for j in range(i, N):
                    if used[j]:
                        new_cost += 1
                if new_cost < cur_min:
                    if index + 1 == N and new_cost < cur_min:
                        cur_min = new_cost
                    else:
                        used[i] = True
                        cur_min = min(cur_min, solve(index + 1, A[i], new_cost, cur_min))
                        used[i] = False
        else:
            if B[i] >= cur_elem:
                cost_delta = 0
                for j in range(i, N):
                    if used[j]:
                        cost_delta += 1
                new_cost = cost + cost_delta
                if new_cost < cur_min:
                    if index + 1 == N and new_cost < cur_min:
                        cur_min = new_cost
                    else:
                        used[i] = True
                        cur_min = min(cur_min, solve(index + 1, B[i], new_cost, cur_min))
                        used[i] = False
    return cur_min

ans = solve(0, -1, 0, 100000)
if ans == 100000:
    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()))

def solve(not_used, index, cur_elem, cost, cur_min):
    #print("\t" * index, cur_elem, cost)
    if index == N:
        return cost
    for i in not_used:
        if (index - i) % 2 == 0:
            if A[i] >= cur_elem:
                cost_delta = 0
                for j in range(i, N):
                    if j not in not_used:
                        cost_delta += 1
                new_cost = cost + cost_delta
                if new_cost < cur_min:
                    cur_min = min(cur_min, solve(not_used - {i}, index + 1, A[i], new_cost, cur_min))
        else:
            if B[i] >= cur_elem:
                cost_delta = 0
                for j in range(i, N):
                    if j not in not_used:
                        cost_delta += 1
                new_cost = cost + cost_delta
                if new_cost < cur_min:
                    cur_min = min(cur_min, solve(not_used - {i}, index + 1, B[i], new_cost, cur_min))
    return cur_min

ans = solve({i for i in range(N)}, 0, -1, 0, 100000)
if ans == 100000:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
dp = [[INF for _ in range(51)] for _ in range(1<<N)]
dp[0][0] = 0
for S in range(1 << N):
  j = bin(S).count("1")
  c = 0
  for i in range(N):
    if not (S & 1<<i):
      if (i - j) % 2 == 0:
        k = A[i]
      else:
        k = B[i]
      for l in range(k+1):
        dp[S|1<<i][k] = min(dp[S|1<<i][k],dp[S][l]+c)
      c += 1
ans = min(dp[-1])
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

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

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

dp = [[INF for i in range(N)] for j in range(1 << N)]

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

for i in range(1 << N):
    for j in range(N):
        if i >> j & 1:
            if (popcount(i) - j) % 2 != 0:
                num = A[j]
            else:
                num = B[j]
            cnt = 0
            for k in range(N):
                if not (i >> k & 1):
                    if (popcount(i) - k) % 2 == 0:
                        num2 = A[k]
                    else:
                        num2 = B[k]
                    if num <= num2:
                        dp[i | 1 << k][k] = min(dp[i | 1 << k][k], dp[i][j] + cnt)
                    cnt += 1

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

if ans == INF:
    print(-1)
else:
    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()]


class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        i += 1
        s = self.one
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


ans = 10 ** 18
for i in range(1 << n):
    c = []
    for j in range(n):
        if i >> j & 1 == 0:
            c.append(a[j])
        else:
            c.append(b[j])
    d = sorted(c)

    ind = {}
    for j, k in enumerate(d):
        if (j % 2, k) not in ind:
            ind[(j % 2, k)] = j

    e = []
    ok = True
    for j, k in enumerate(c):
        j = ((i >> j & 1) + j) % 2
        if (j, k) not in ind:
            ok = False
            break
        l = ind[(j, k)]
        if l >= n or d[l] != k:
            ok = False
            break
        e.append(l)
        ind[(j, k)] += 2

    if ok:
        count = 0
        bit = BIT([0] * (n+1))
        for j in e:
            count += bit.get(n - j)
            bit.update(n-j, 1)
        ans = min(ans, count)
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())) for _ in range(2)]
dp = [[1000]*(2**n) for _ in range(51)]
dp[0][0] = 0
for S in range(2**n):
  j = bin(S).count("1")
  for i in range(n):
    if not (S & 1<<i):
      cnt = bin(S)[2:].zfill(n)[n-i:].count("0")
      k = a[(i+j)%2][i]
      for l in range(k+1):
        dp[k][S|1<<i] = min(dp[k][S|1<<i],dp[l][S]+cnt)
ans = min(dp[i][-1] for i in range(51))
if ans == 1000:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

INF = 1<<20

dp = [[INF] * 55 for i in range(1<<n)]
dp[0][0] = 0

for b in range(1<<n):
    # 使ったカードの枚数
    bitcnt = bin(b).count("1")
    cur = bitcnt 
    rest = [] 
    for i in range(n):
        # i番目のbitが立っているかの判定
        if not (b & (1 << i)):
            rest.append((i,cur))
            cur += 1
    # A,Bの制約から、sは55まででOK
    for s in range(51):
        if dp[b][s] >= INF:
            continue
        # 残ったカードで更新
        for i,cur in rest:
            if abs(bitcnt - i) % 2 == 0:
                num = As[i]
            else:
                num = Bs[i]
            if num >= s:
                d = abs(bitcnt - cur) 
                dp[b|(1<<i)][num] = min(dp[b|(1<<i)][num], dp[b][s] + d)
            

ans = min(dp[(1<<n)-1])
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time

def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    A = LI()
    B = LI()
    ans = IINF

    for idxs in permutations([i for i in range(N)]):
        idxs = list(idxs)
        front = []
        for pos in range(len(idxs)):
            idx = idxs[pos]
            if pos % 2 == 0 and idx % 2 == 0:
                front.append(A[idx])
            elif pos % 2 == 0 and idx % 2 == 1:
                front.append(B[idx])
            elif pos % 2 == 1 and idx % 2 == 0:
                front.append(B[idx])
            elif pos % 2 == 1 and idx % 2 == 1:
                front.append(A[idx])

        if all([front[i-1] <= front[i] for i in range(1, N)]):
            swap_count = sum([abs(pos - idxs[pos]) for pos in range(len(idxs))]) // 2
            ans = min(ans, swap_count)

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



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

    def add(self, index, x):
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1


INF = 10**18

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

res = INF

for i in range(2**N):
    front = []
    back = []
    for j in range(N):
        if (i >> j) & 1:
            front.append((A[j], j))
        else:
            back.append((B[j], j))
    odd = []
    even = []
    for x, j in front:
        if j % 2 == 0:
            odd.append((x, j))
        else:
            even.append((x, j))
    for x, j in back:
        if j % 2 != 0:
            odd.append((x, j))
        else:
            even.append((x, j))
    if len(even) != N // 2:
        continue
    odd.sort()
    even.sort()
    seq = []
    for j in range(N):
        if j % 2 == 0:
            seq.append(odd[j // 2])
        else:
            seq.append(even[j // 2])
    for j in range(N - 1):
        if seq[j][0] > seq[j + 1][0]:
            break
    else:
        bit = BinaryIndexedTree(N)
        count = 0
        for j in range(N):
            bit.add(seq[j][1] + 1, 1)
            count += j + 1 - bit.sum(seq[j][1] + 1)
        res = min(res, count)

print(res if res != INF else -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

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] not in l and card[0] < p and card[1] < p:
            return ret
    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 - set(card), l+[card[2]], card[(i-(card[2]+1))%2]))
    return ret

ans = dp(set(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

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] not in l and card[0] < p and card[1] < p:
            return ret
    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 - set(card), l+[card[2]], card[(i-(card[2]+1))%2]))
    dic[tuple(l)] = ret
    return ret

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def solve():
    INF = 10**5

    def getNumInversion(odrAs):
        def makeBIT(numEle):
            numPow2 = 2 ** (numEle-1).bit_length()
            data = [0] * (numPow2+1)
            return data, numPow2
        def addValue(iA, A):
            iB = iA + 1
            while iB <= numPow2:
                data[iB] += A
                iB += iB & -iB
        def getSum(iA):
            iB = iA + 1
            ans = 0
            while iB > 0:
                ans += data[iB]
                iB -= iB & -iB
            return ans
        lenA = len(odrAs)
        data, numPow2 = makeBIT(lenA)
        ans = 0
        for odrA in reversed(odrAs):
            ans += getSum(odrA)
            addValue(odrA, 1)
        return ans

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    ans = INF
    for iEvens in combinations(range(N), r=N//2):
        iEvens = set(iEvens)
        COdds, CEvens = [], []
        for i in range(N):
            if i in iEvens:
                if i % 2:
                    CEvens.append((As[i], i))
                else:
                    CEvens.append((Bs[i], i))
            else:
                if i % 2:
                    COdds.append((Bs[i], i))
                else:
                    COdds.append((As[i], i))
        COdds.sort()
        CEvens.sort()

        Cs = []
        for COdd, CEven in zip(COdds, CEvens):
            Cs += [COdd, CEven]
        if N % 2:
            Cs += [COdds[-1]]

        for i in range(N-1):
            if Cs[i][0] > Cs[i+1][0]:
                break
        else:
            odrAs = [i for C, i in Cs]
            num = getNumInversion(odrAs)
            ans = min(ans, num)

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


solve()

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 - set(card), l+[card[2]], card[(i-(card[2]+1))%2]))
    dic[tuple(l)] = ret
    return ret

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