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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
nums = [None]*n

### BIT 
def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


# 転倒数を求める例
def tento(l):
    n = len(l)
    # 1-indexedなので注意
    bit = [0] * (n+1)
    ans = 0
    for i,ind in enumerate(l):
        ans += (i - query(bit, ind+1))
        update(bit, ind+1, 1)
    return ans


def pp(func):
    def wrapped(*args, **keys):
        print(args, keys)
        val = func(*args, **keys)
        print(val)
        return val
    return wrapped

# @pp
def sub(fr, to, bb):
    # frをtoのいずれかに対応付ける
    elist = []
    olist = []
    for ff,bbb in zip(fr, bb):
        if (ff+bbb)%2:
            olist.append(ff)
        else:
            elist.append(ff)

    elist2 = []
    olist2 = []
    for item in to:
        if item%2:
            olist2.append(item)
        else:
            elist2.append(item)
    if len(olist2)==len(olist) and len(elist2)==len(elist):
        olist.sort()
        elist.sort()
        if to[0]%2==0:
            res = [(elist if i%2==0 else olist)[i//2] for i in range(len(to))]
            return res
        else:
            res = [(olist if i%2==0 else elist)[i//2] for i in range(len(to))]
            return res
    else:
        return None
    
    
best = 10**9
for bit in range(1<<n):
    for i in range(n):
        val = b[i] if bit>>i&1 else a[i]
        nums[i] = (val, i, bit>>i&1)
    nums.sort()
    prev, fr, bb = nums[0]
    to = [0]
    fr = [fr]
    bb = [bb]
    valid = True
    array = []
    for i in range(1,n):
        cv, cfr, cbb = nums[i]
        if prev!=cv:
            res = sub(fr, to, bb)
            if res is None:
                valid = False
                break
            array.extend(res)
            prev, fr, bb = cv, [cfr], [cbb]
            to = [i]
        else:
            fr.append(cfr)
            to.append(i)
            bb.append(cbb)
    else:
        res = sub(fr, to, bb)
        if res is None:
            valid = False
        else:
            array.extend(res)
    if valid:
        ans = tento(array)
#         print(array)
        best = min(best, ans)
#         print(nums, ans)
if best==10**9:
    print(-1)
else:
    print(best)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from itertools import permutations,combinations
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 全探索
INF = 10 ** 5
answer = INF
N = ir()
if N == 1:
    print(0); exit()
A = lr()
B = lr()
for pattern in combinations(range(N), (N+1)//2):
    pattern = set(pattern)
    red = []
    blue = []
    for i in range(N):
        if i in pattern:
            red.append((B[i], i) if i&1 else (A[i], i))
        else:
            blue.append((A[i], i) if i&1 else (B[i], i))
    red.sort()
    blue.sort()
    result = []
    
    for i in range(N//2):
        if red[i][0] > blue[i][0]:
            break
        if i + 1 < len(red) and red[i+1][0] < blue[i][0]:
            break
        result.append(red[i][1])
        result.append(blue[i][1])
    else:
        if N&1 and blue[-1][0] > red[-1][0]:
            continue
        if N&1:
            result.append(red[-1][1])
        temp = 0
        used = set()
        for i in range(N):
            for x in used:
                if result[i] < x:
                    temp += 1
            used.add(result[i])            
        if temp < answer:
            answer = temp

print(answer if answer != INF else -1)
# 12

Submission status: Accepted

Solution code:
def examA():
    H = I()
    W = I()
    N = I()
    ans = (N-1)//max(H,W) + 1
    print(ans)
    return

def examB():
    N = I()
    XL = [LI()for _ in range(N)]
    for i in range(N):
        XL[i][0] += XL[i][1]
    XL.sort()
#    print(XL)
    ans = 0
    now = -inf
    for i in range(N):
        if XL[i][0]-XL[i][1]*2>=now:
            ans +=1
            now = XL[i][0]
    print(ans)
    return

def examC():
    N, K, S = LI()
    A = [0]*N
    if S>=10**6:
        a = 1
    else:
        a = S+1
    for i in range(N):
        if i<K:
            A[i] = S
        else:
            A[i] = a
    print(" ".join(map(str,A)))
    return

def examD():
    N = I()
    A = LI()
    B = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cur = 0
        nowA = []
        l = -1; r = 0
        for j in range(N):
            if i&(1<<j)==(1<<j):
                cur +=1
                nowA.append(B[j])
                if l==-1:
                    l = j
                r = j+1
            else:
                nowA.append(A[j])
        if cur%2==1:
            continue
        if l==-1:
            l = 0
        pr = sorted(nowA)
#        print(nowA,pr)
        now = 0
        for j in range(N):
            dist = [i for i, x in enumerate(pr) if x == nowA[j]]
#            print(dist)
            candi = inf
            for v in dist:
                if ((abs(v-j)%2)==1 and i&(1<<j)==(1<<j)):
                    candi = min(candi,abs(v-j))
                if ((abs(v-j)%2)==0 and i&(1<<j)==0):
                    candi = min(candi,abs(v-j))
            if candi==inf:
#                print(dist, i & (1 << j),i,j)
                now = inf
                break
            else:
                if candi==0 and l<=j<r:
                    candi = 2
                now +=candi
#        if (now//2)%2==(r-l)%2:
        ans = min(ans,now)
#        print(now)
    if ans==inf:
        print(-1)
    else:
        print(ans//2)
    return

def examD2():
    # 0は絶対に入れない!!
    class Bit():
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
            return

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x=1):
            # i==0 はだめ => 全部+1するとか
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
            # maspyさんの参考　よくわかってない
            i = 0
            s = 0
            step = 1 << ((self.size).bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i + 1

        def debug(self, k):
            return [self.sum(i) for i in range(k)]

        def inversion(self, A=[3, 10, 1, 8, 5]):
            res = 0
            for i, p in enumerate(A):
                self.add(p, 1)
                res += i + 1 - self.sum(p)
            return res

    N = I()
    A = LI()
    B = LI()
    ans = inf
    loop = 1<<N
    for l in range(loop):
        LO = []
        LE = []
        for j in range(N):
            if l&(1<<j)>0:
                if j%2==0:
                    LE.append((B[j],j+1))
                else:
                    LO.append((B[j],j+1))
            else:
                if j%2==0:
                    LO.append((A[j],j+1))
                else:
                    LE.append((A[j],j+1))
        if (len(LO)-len(LE))!=N%2:
            continue
        LO.sort()
        LE.sort()
        L = []
        L.append(LO[0][1])
        flag = True
        for i in range(1,N):
            if i%2==1:
                if LE[i//2][0]>=LO[i//2][0]:
                    L.append(LE[i//2][1])
                else:
                    flag = False
                    break
            else:
                if LO[i//2][0]>=LE[i//2-1][0]:
                    L.append(LO[i//2][1])
                else:
                    flag = False
                    break

        if flag:
            bit = Bit(N+1)
            now = bit.inversion(L)
            if ans > now:
                ans = now
    if ans==inf:
        ans = -1
    print(ans)
    return

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

    UP = (N + 1) // 2
    DOWN = N - UP

    ANS = 1 << 31

    def ten(A):
        LEN = len(A)
        MAX = max(A)
        MIN = min(A)

        BIT = [0] * (MAX - MIN + 2)  # 出現回数をbit indexed treeの形でもっておく.

        def update(v, w):  # index vにwを加える
            while v <= MAX - MIN + 1:
                BIT[v] += w
                v += (v & (-v))  # 自分を含む大きなノードへ. たとえばv=3→v=4

        def getvalue(v):  # MIN～vの区間の和を求める
            ANS = 0
            while v != 0:
                ANS += BIT[v]
                v -= (v & (-v))  # たとえばv=3→v=2へ
            return ANS

        ANS = 0
        for i in range(LEN):  # A[0],A[1],...とBITを更新しながら,各A[i]について転倒数を求める.
            bit_ai = A[i] - MIN + 1  # A[i]がBITの中で何番目か

            ANS += i  # 今まで出現した個数.
            ANS -= getvalue(bit_ai)  # 今まで出現した中で,MIN～bit_aiの個数を減らす.
            # bit_ai～MAXの出現個数が転倒数

            update(bit_ai, 1)

        return ANS

    for i in range(1 << N):
        UD = [0, 0]
        S0 = []
        S1 = []

        for j in range(N):
            if (1 << j) & i != 0:
                if j % 2 == 0:
                    S0.append((A[j], j))
                else:
                    S1.append((A[j], j))
                UD[j % 2] += 1

            else:
                if (j + 1) % 2 == 0:
                    S0.append((B[j], j))
                else:
                    S1.append((B[j], j))

                UD[(j + 1) % 2] += 1

        if UD[0] == UP and UD[1] == DOWN:
            S0.sort()
            S1.sort()
            # print(UD,S0,S1)

            for i in range(1, N):
                if i % 2 == 0:
                    if S0[i // 2][0] >= S1[(i - 1) // 2][0]:
                        True
                    else:
                        break
                else:
                    if S1[i // 2][0] >= S0[(i - 1) // 2][0]:
                        True
                    else:
                        break
            else:
                K = []
                for i in range(N):
                    if i % 2 == 0:
                        K.append(S0[i // 2][1])
                    else:
                        K.append(S1[i // 2][1])

                # print(K)
                # print(ten(K))

                ANS = min(ANS, ten(K))

    if ANS == 1 << 31:
        print(-1)
    else:
        print(ANS)
    return

def examE():
    return

from copy import deepcopy
import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD2()

"""
4
5 2 3 4
2 8 4 2
"""

Submission status: Accepted

Solution code:
def examA():
    H = I()
    W = I()
    N = I()
    ans = (N-1)//max(H,W) + 1
    print(ans)
    return

def examB():
    N = I()
    XL = [LI()for _ in range(N)]
    for i in range(N):
        XL[i][0] += XL[i][1]
    XL.sort()
#    print(XL)
    ans = 0
    now = -inf
    for i in range(N):
        if XL[i][0]-XL[i][1]*2>=now:
            ans +=1
            now = XL[i][0]
    print(ans)
    return

def examC():
    N, K, S = LI()
    A = [0]*N
    if S>=10**6:
        a = 1
    else:
        a = S+1
    for i in range(N):
        if i<K:
            A[i] = S
        else:
            A[i] = a
    print(" ".join(map(str,A)))
    return

def examD():
    N = I()
    A = LI()
    B = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cur = 0
        nowA = []
        l = -1; r = 0
        for j in range(N):
            if i&(1<<j)==(1<<j):
                cur +=1
                nowA.append(B[j])
                if l==-1:
                    l = j
                r = j+1
            else:
                nowA.append(A[j])
        if cur%2==1:
            continue
        if l==-1:
            l = 0
        pr = sorted(nowA)
#        print(nowA,pr)
        now = 0
        for j in range(N):
            dist = [i for i, x in enumerate(pr) if x == nowA[j]]
#            print(dist)
            candi = inf
            for v in dist:
                if ((abs(v-j)%2)==1 and i&(1<<j)==(1<<j)):
                    candi = min(candi,abs(v-j))
                if ((abs(v-j)%2)==0 and i&(1<<j)==0):
                    candi = min(candi,abs(v-j))
            if candi==inf:
#                print(dist, i & (1 << j),i,j)
                now = inf
                break
            else:
                if candi==0 and l<=j<r:
                    candi = 2
                now +=candi
#        if (now//2)%2==(r-l)%2:
        ans = min(ans,now)
#        print(now)
    if ans==inf:
        print(-1)
    else:
        print(ans//2)
    return

def examD2():
    # 0は絶対に入れない!!
    class Bit():
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
            return

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x=1):
            # i==0 はだめ => 全部+1するとか
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
            # maspyさんの参考　よくわかってない
            i = 0
            s = 0
            step = 1 << ((self.size).bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i + 1

        def debug(self, k):
            return [self.sum(i) for i in range(k)]

        def inversion(self, A=[3, 10, 1, 8, 5]):
            res = 0
            for i, p in enumerate(A):
                self.add(p, 1)
                res += i + 1 - self.sum(p)
            return res

    N = I()
    A = LI()
    B = LI()
    ans = inf
    loop = 1<<N
    for l in range(loop):
        LO = []
        LE = []
        for j in range(N):
            if l&(1<<j)>0:
                if j%2==0:
                    LE.append((B[j],j+1))
                else:
                    LO.append((B[j],j+1))
            else:
                if j%2==0:
                    LO.append((A[j],j+1))
                else:
                    LE.append((A[j],j+1))
        if (len(LO)-len(LE))!=N%2:
            continue
        LO.sort()
        LE.sort()
        L = []
        L.append(LO[0][1])
        flag = True
        for i in range(1,N):
            if i%2==1:
                if LE[i//2][0]>=LO[i//2][0]:
                    L.append(LE[i//2][1])
                else:
                    flag = False
                    break
            else:
                if LO[i//2][0]>=LE[i//2-1][0]:
                    L.append(LO[i//2][1])
                else:
                    flag = False
                    break

        if flag:
            bit = Bit(51)
            now = bit.inversion(L)
            if ans > now:
                ans = now
    if ans==inf:
        ans = -1
    print(ans)
    return

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

    UP = (N + 1) // 2
    DOWN = N - UP

    ANS = 1 << 31

    def ten(A):
        LEN = len(A)
        MAX = max(A)
        MIN = min(A)

        BIT = [0] * (MAX - MIN + 2)  # 出現回数をbit indexed treeの形でもっておく.

        def update(v, w):  # index vにwを加える
            while v <= MAX - MIN + 1:
                BIT[v] += w
                v += (v & (-v))  # 自分を含む大きなノードへ. たとえばv=3→v=4

        def getvalue(v):  # MIN～vの区間の和を求める
            ANS = 0
            while v != 0:
                ANS += BIT[v]
                v -= (v & (-v))  # たとえばv=3→v=2へ
            return ANS

        ANS = 0
        for i in range(LEN):  # A[0],A[1],...とBITを更新しながら,各A[i]について転倒数を求める.
            bit_ai = A[i] - MIN + 1  # A[i]がBITの中で何番目か

            ANS += i  # 今まで出現した個数.
            ANS -= getvalue(bit_ai)  # 今まで出現した中で,MIN～bit_aiの個数を減らす.
            # bit_ai～MAXの出現個数が転倒数

            update(bit_ai, 1)

        return ANS

    for i in range(1 << N):
        UD = [0, 0]
        S0 = []
        S1 = []

        for j in range(N):
            if (1 << j) & i != 0:
                if j % 2 == 0:
                    S0.append((A[j], j))
                else:
                    S1.append((A[j], j))
                UD[j % 2] += 1

            else:
                if (j + 1) % 2 == 0:
                    S0.append((B[j], j))
                else:
                    S1.append((B[j], j))

                UD[(j + 1) % 2] += 1

        if UD[0] == UP and UD[1] == DOWN:
            S0.sort()
            S1.sort()
            # print(UD,S0,S1)

            for i in range(1, N):
                if i % 2 == 0:
                    if S0[i // 2][0] >= S1[(i - 1) // 2][0]:
                        True
                    else:
                        break
                else:
                    if S1[i // 2][0] >= S0[(i - 1) // 2][0]:
                        True
                    else:
                        break
            else:
                K = []
                for i in range(N):
                    if i % 2 == 0:
                        K.append(S0[i // 2][1])
                    else:
                        K.append(S1[i // 2][1])

                # print(K)
                # print(ten(K))

                ANS = min(ANS, ten(K))

    if ANS == 1 << 31:
        print(-1)
    else:
        print(ANS)
    return

def examE():
    return

from copy import deepcopy
import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD2()

"""
4
5 2 3 4
2 8 4 2
"""

Submission status: Accepted

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

dp = [[10**9 for _ in range(51)] for __ in range(1 << n)]
dp[0][0] = 0


for i in range(1 << n):
    target = bin(i).count("1")-1
    cnt = bin(i).count("1")
    for j in range(n):
        if i >> j & 1:
            cnt -= 1
            if abs(j - target) % 2 == 0:
                nxt = a[j]
            else:
                nxt = b[j]
            for k in range(nxt+1):
                if dp[i ^ (1 << j)][k] != 10**9:
                    dp[i][nxt] = min(dp[i][nxt], dp[i ^ (1 << j)][k] + abs(j+cnt-target))

ans = min(dp[2**n-1])

print(ans if ans < 10**9 else -1)

Submission status: Accepted

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

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
        for k in range(n):
            for j in range(n - 1 - k):
                if e[j] > e[j + 1]:
                    count += 1
                    e[j], e[j + 1] = e[j + 1], e[j]
        ans = min(ans, count)
if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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
        for _ in range(n):
            for j in range(n - 1):
                if e[j] > e[j + 1]:
                    count += 1
                    e[j], e[j + 1] = e[j + 1], e[j]
        ans = min(ans, count)
if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

ans=float("inf")
count=0
def dfs(num,ro,re,bo,be):
    global ans,count
    count+=1
    if num==N:
        que=[]
        ro.sort(reverse=True)
        re.sort(reverse=True)
        bo.sort(reverse=True)
        be.sort(reverse=True)
        ropos=-1
        repos=-1
        bopos=-1
        bepos=-1
        for i in range(N):
            if i%2==0:
                if repos>=-len(re) and bopos>=-len(bo):
                    val1,num1=re[repos]
                    val2,num2=bo[bopos]
                    if val1>val2:
                        que.append([val2,num2])
                        bopos-=1
                    elif val2>val1:
                        que.append([val1,num1])
                        repos-=1
                    elif num1>num2:
                        que.append([val2,num2])
                        bopos-=1
                    else:
                        que.append([val1,num1])
                        repos-=1
                elif repos>=-len(re):
                    val,num=re[repos]
                    que.append([val,num])
                    repos-=1
                elif bopos>=-len(bo):
                    val,num=bo[bopos]
                    que.append([val,num])
                    bopos-=1
                else:
                    return 0
            else:
                if ropos>=-len(ro) and bepos>=-len(be):
                    val1,num1=ro[ropos]
                    val2,num2=be[bepos]
                    if val1>val2:
                        que.append([val2,num2])
                        bepos-=1
                    elif val2>val1:
                        que.append([val1,num1])
                        ropos-=1
                    elif num1>num2:
                        que.append([val2,num2])
                        bepos-=1
                    else:
                        que.append([val1,num1])
                        ropos-=1
                elif ropos>=-len(ro):
                    val,num=ro[ropos]
                    que.append([val,num])
                    ropos-=1
                elif bepos>=-len(be):
                    val,num=be[bepos]
                    que.append([val,num])
                    bepos-=1
                else:
                    return 0


        for i in range(1,N):
            if que[i][0]<que[i-1][0]:
                return 0

        temp=0
        for i in range(1,N):
            for j in range(0,i):
                if que[i][1]<que[j][1]:
                    temp+=1
        ans=min(ans,temp)
        return 0

    if num%2==0:
        dfs(num+1,ro,re+[[A[num],num]],bo,be)
        dfs(num+1,ro,re,bo,be+[[B[num],num]])
    else:
        dfs(num+1,ro+[[A[num],num]],re,bo,be)
        dfs(num+1,ro,re,bo+[[B[num],num]],be)

dfs(0,[],[],[],[])
print(ans if ans!=float("inf") else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = float('inf')
for b in range(1 << N):
    even = []
    odd = []
    for i in range(N):
        if b >> i & 1:  # red
            if i % 2 == 0:
                even.append((A[i], i))
            else:
                odd.append((A[i], i))
        else:  # blue
            if i % 2 == 0:
                odd.append((B[i], i))
            else:
                even.append((B[i], i))
    if len(even) != (N + 1) // 2 or len(odd) != N // 2:
        continue
    even.sort()
    odd.sort()
    num = []
    for i in range(len(odd)):
        num += [even[i], odd[i]]
    if N % 2 == 1:
        num += [even[-1]]
    ok = True
    for i in range(N-1):
        if num[i][0] > num[i+1][0]:
            ok = False
            break
    if not ok:
        continue
    tmp = 0
    bit = BIT(N)
    for i in range(1, N):
        bit.add(i, 1)
    for i in range(N):
        j = num[i][1]
        tmp += bit.sum(j) - i
        bit.add(0, 1)
        bit.add(j, -1)
    ans = min(ans, tmp)
print(ans if ans < float('inf') else -1)

Submission status: Accepted

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")
  cnt = 0
  for i in range(n):
    if not (S & 1<<i):
      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)
    if not (S&1<<i):
      cnt += 1
ans = min(dp[i][-1] for i in range(51))
if ans == 1000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

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

ans = 200
for bit in range(1<<n):
	if sum(list(map(int, list(bin(bit)[2:])))) %2 == 1:
		continue
	if sum([(i%2) ^ ((bit>>i)&1) for i in range(n)]) != n//2:
		continue
	c = [[b[i], i, (i%2) ^ ((bit>>i)&1)] if (bit>>i)&1 == True else [a[i], i, (i%2) ^ ((bit>>i)&1)] for i in range(n)]
	#print(bit, c)
	even = 0
	odd = 1
	c.sort(key=lambda x: (x[0], x[1]))
	#print(c)
	goal = [-1 for _ in range(n)]
	for i, p in enumerate(c):
		x, y, z = p
		if z == 0:
			goal[even] = [x, y]
			even += 2
		else:
			goal[odd] = [x, y]
			odd += 2
	#print(goal)
	ok = True
	for i in range(n-1):
		if goal[i][0] > goal[i+1][0]:
			ok = False
			break
	if not ok:
		continue

	tmp = 0
	st = Rsum(n)
	for x, y in goal:
		tmp += st.Get(y, n)
		st.Add(y, 1)
	ans = min(ans, tmp)

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

Submission status: Accepted

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