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:
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):
        O = defaultdict(int)
        E = defaultdict(int)
        L = []
        for j in range(N):
            if l&(1<<j)>0:
                if j%2==0:
                    E[B[j]] += 1
                    L.append(B[j])
                else:
                    O[B[j]] += 1
                    L.append(B[j])
            else:
                if j%2==0:
                    O[A[j]] += 1
                    L.append(A[j])
                else:
                    E[A[j]] += 1
                    L.append(A[j])
        if (len(O)-len(E))!=N%2:
            continue
        C = deepcopy(L)
        L.sort()
        for i,l in enumerate(L):
            if i%2==0:
                O[l] -= 1
            else:
                E[l] -= 1
        flag = True
        for o in O.values():
            if o!=0:
                flag = False
                break
        for e in E.values():
            if e!=0:
                flag = False
                break
        if flag:
            bit = Bit(51)
            now = bit.inversion(C)
            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: Wrong Answer

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):
        O = defaultdict(int)
        E = defaultdict(int)
        L = []
        for j in range(N):
            if l&(1<<j)>0:
                if j%2==0:
                    E[B[j]] += 1
                    L.append(B[j])
                else:
                    O[B[j]] += 1
                    L.append(B[j])
            else:
                if j%2==0:
                    O[A[j]] += 1
                    L.append(A[j])
                else:
                    E[A[j]] += 1
                    L.append(A[j])
        if (len(O)-len(E))!=N%2:
            continue
        bit = Bit(51)
        now = bit.inversion(L)
        L.sort()
        for i,l in enumerate(L):
            if i%2==0:
                O[l] -= 1
            else:
                E[l] -= 1
        flag = True
        for o in O.values():
            if o!=0:
                flag = False
                break
        for e in E.values():
            if e!=0:
                flag = False
                break
        if flag and 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

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: Wrong Answer

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 = 2**N
    for l in range(loop):
        O = defaultdict(int)
        E = defaultdict(int)
        L = []
        for j in range(N):
            if (l&(1<<j)>0 and j%2==0):
                E[B[j]] += 1
                L.append(B[j])
            elif (l & (1 << j) == 0 and j % 2 == 1):
                E[A[j]] += 1
                L.append(A[j])
            elif (l&(1<<j)>0 and j%2==1):
                O[B[j]] += 1
                L.append(B[j])
            else:
                O[A[j]] += 1
                L.append(A[j])
        bit = Bit(51)
        now = bit.inversion(L)
        L.sort()
        for i,l in enumerate(L):
            if i%2==0:
                O[l] -= 1
            else:
                E[l] -= 1
        flag = True
        for o in O.values():
            if o!=0:
                flag = False
        for e in E.values():
            if e!=0:
                flag = False
        if flag:
            ans = min(ans,now)
    if ans==inf:
        ans = -1
    print(ans)
    return

def examE():
    return

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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

class BIT:
    def __init__(self,n):
        self.num=n
        self.dat=[0]*(self.num+1)
        self.depth=n.bit_length()
    
    def add(self,i,x):
        i+=1
        while i<=self.num:
            self.dat[i]+=x
            i+=i&-i
    
    def sum(self,i):
        i+=1
        s=0
        while i>0:
            s+=self.dat[i]
            i-=i&-i
        return s
    
    def lower_bound(self,x):
        sum_=0
        pos=0
        for i in range(self.depth,-1,-1):
            k=pos+(1<<i)
            if k<=self.num and sum_+self.dat[k]<x:
                sum_+=self.dat[k]
                pos+=1<<i
        return pos, sum_

ans=INF
for i in range(2**N):
    ura=0
    C=[]
    odd=[]
    even=[]
    for j in range(N):
        if (i>>j)&1:
            ura+=1
            C.append(B[j])
            if j%2:
                even.append(B[j])
            else:
                odd.append(B[j])
        else:
            C.append(A[j])
            if j%2:
                odd.append(A[j])
            else:
                even.append(A[j])
    if ura%2:
        continue
    codd=Counter(odd)
    ceven=Counter(even)
    D=C[:]
    D.sort()
    f=False
    for j in range(N):
        if j%2:
            if codd[D[j]]>0:
                codd[D[j]]-=1
            else:
                f=True
                break
        else:
            if ceven[D[j]]>0:
                ceven[D[j]]-=1
            else:
                f=True
                break
    if f:
        continue
    bo=BIT(51)
    be=BIT(51)
    tmp=0
    for j in range(-(-N//2)):
        be.add(even[j],1)
        tmp+=j+1-be.sum(even[j])
        if j<(-(-N//2))-1 or N%2==0:
            bo.add(odd[j],1)
            tmp+=j+1-be.sum(odd[j])
    tmp*=2
    tmp+=ura
    tmp//=2
    ans=min(ans,tmp)
print(ans if ans!=INF else -1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

class BIT:
    def __init__(self,n):
        self.num=n
        self.dat=[0]*(self.num+1)
        self.depth=n.bit_length()
    
    def add(self,i,x):
        i+=1
        while i<=self.num:
            self.dat[i]+=x
            i+=i&-i
    
    def sum(self,i):
        i+=1
        s=0
        while i>0:
            s+=self.dat[i]
            i-=i&-i
        return s
    
    def lower_bound(self,x):
        sum_=0
        pos=0
        for i in range(self.depth,-1,-1):
            k=pos+(1<<i)
            if k<=self.num and sum_+self.dat[k]<x:
                sum_+=self.dat[k]
                pos+=1<<i
        return pos, sum_

ans=INF
for i in range(2**N):
    ura=0
    C=[]
    odd=[]
    even=[]
    for j in range(N):
        if (i>>j)&1:
            ura+=1
            C.append(B[j])
            if j%2:
                even.append(B[j])
            else:
                odd.append(B[j])
        else:
            C.append(A[j])
            if j%2:
                odd.append(A[j])
            else:
                even.append(A[j])
    if ura%2:
        continue
    codd=Counter(odd)
    ceven=Counter(even)
    D=C[:]
    D.sort()
    f=False
    for j in range(N):
        if j%2:
            if codd[D[j]]>0:
                codd[D[j]]-=1
            else:
                f=True
                break
        else:
            if ceven[D[j]]>0:
                ceven[D[j]]-=1
            else:
                f=True
                break
    if f:
        continue
    b=BIT(51)
    tmp=0
    for j,x in enumerate(C):
        b.add(x,1)
        tmp+=j+1-b.sum(x)
    ans=min(ans,tmp)
print(ans if ans!=INF else -1)

Submission status: Wrong Answer

Solution code:
import sys


class Solution:
    def __init__(self):
        self.minimum = sys.maxsize

    def check(self, cards):
        for i in range(len(cards) - 1):
            if cards[i][0] > cards[i + 1][0]:
                return False
        return True

    def swapAndFlip(self, i, j, cards):
        cards[i], cards[j] = cards[j], cards[i]
        cards[i][0], cards[i][1] = cards[i][1], cards[i][0]
        cards[j][0], cards[j][1] = cards[j][1], cards[j][0]

    def dfs(self, start, ops, cards):
        if start == len(cards):
            if self.check(cards):
                self.minimum = min(self.minimum, ops)
            return
        self.dfs(start + 1, ops, cards)
        for i in range(start + 1, len(cards)):
            self.swapAndFlip(start, i, cards)
            ops += 1
            self.dfs(start + 1, ops, cards)
            self.swapAndFlip(start, i, cards)
            ops -= 1

    def minNumOperations(self, upSides, downSides):
        self.minimum = sys.maxsize
        self.dfs(0, 0, [[upSides[x], downSides[x]] for x in range(len(upSides))])
        return self.minimum if self.minimum < sys.maxsize else -1


if __name__ == '__main__':
    N = int(sys.stdin.readline().strip())
    REDs = list(map(int, sys.stdin.readline().strip().split()))
    BLUEs = list(map(int, sys.stdin.readline().strip().split()))
    solution = Solution()
    print(solution.minNumOperations(REDs, BLUEs))
    # print(solution.minNumOperations([3, 4, 3], [3, 2, 3]))
    # print(solution.minNumOperations([2, 1], [1, 2]))
    # print(solution.minNumOperations([1, 2, 3, 4], [5, 6, 7, 8]))
    # print(solution.minNumOperations([28, 15, 22, 43, 31], [20, 22, 43, 33, 32]))
    # print(solution.minNumOperations([4, 46, 6, 38, 43], [33, 15, 18, 27, 37]))

Submission status: Wrong Answer

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] > num[i+1]:
            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: Wrong Answer

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, 1))
            else:
                odd.append((A[i], i, 1))
        else:  # blue
            if i % 2 == 0:
                odd.append((B[i], i, 0))
            else:
                even.append((B[i], i, 0))
    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] > num[i+1]:
            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: Wrong Answer

Solution code:
# 位置で表裏確定
# 表裏固定でソート
# 辻褄合うか
# 番号同じ場合は？
n=int(input())
*a,=map(int, input().split( ))
*b,=map(int, input().split( ))

ans= 1000
bit = 1<<n
for i in range(bit):
    c=[(a[j],j) if (i>>j)&1 else (b[j],j) for j in range(n)]
    c.sort()
    can = True
    cnt=0
    for j in range(n):
        if (c[j][1]-j)%2==0:
            if a[c[j][1]]!=c[j][0]:
                can=False
                break
        else:
            if b[c[j][1]]!=c[j][0]:
                can=False
                break
        cnt+=abs(c[j][1]-j)
    if not can:
        continue
    ans=min(ans,cnt//2)
if ans==1000:
    print(-1)
else:
    print(ans)