Problem:


Score : 700 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 18

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
3 4 3
3 2 3

Sample Output 1

1

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

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

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

Sample Input 3

4
1 2 3 4
5 6 7 8

Sample Output 3

0

No operation may be required.

Sample Input 4

5
28 15 22 43 31
20 22 43 33 32

Sample Output 4

-1

Sample Input 5

5
4 46 6 38 43
33 15 18 27 37

Sample Output 5

3



Sample input:
3
3 4 3
3 2 3


Sample output:
1

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def swap(l):
    cnt = 0
    now = list(range(n))
    for i in range(n):
        c = l[n-i-1]
        n_ind = now.index(c)
        # print(n_ind)
        cnt += abs((n-i-1)-n_ind)
        if (n-i-1)-n_ind == 0:
            continue
        now.remove(c)
        # print(now)
        now.insert(n-i-1,c)
        # print(now)
    return cnt

n = inp()
a = inpl()
b = inpl()
card = []
res = INF
for i in range(n):
    card.append([a[i],b[i],i])
for flag in itertools.combinations(range(n),(n+1)//2):
    # print(flag)
    f = True
    odd_li = []
    odd_ind = [False] * n
    for i,bit in enumerate(flag):
        c = 1 if bit%2 else 0
        odd_li.append([card[bit][c],bit])
        odd_ind[bit] = True
    if not f:
        continue
    odd_li.sort()
    even_li = []
    for i in range(n):
        c = 0 if i%2 else 1
        if not odd_ind[i]:
            even_li.append([card[i][c],i])
    even_li.sort()
    # print(odd_li,even_li)

    if n%2:
        for i in range(n//2):
            if odd_li[i][0] <= even_li[i][0] <= odd_li[i+1][0]:
                continue
            else:
                f = False; break
    else:
        for i in range(n//2):
            if i != n//2-1:
                if odd_li[i][0] <= even_li[i][0] <= odd_li[i+1][0]:
                    continue
                else:
                    f = False; break
            else:
                if odd_li[-1][0] <= even_li[-1][0]:
                    continue
                else:
                    f = False; break

    if f:
        after_ind = []
        for i in range(n//2):
            after_ind.append(odd_li[i][1])
            after_ind.append(even_li[i][1])
        if n%2:
            after_ind.append(odd_li[-1][1])
        # print(odd_li,even_li)
        # print(after_ind)
        res = min(res,swap(after_ind))
print(-1 if res == INF else res)

Submission status: Accepted

Solution code:

N = int(input())

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

for ii in range(2 ** N):

    s = format(ii,'b').zfill(N)
    on = 0
    
    for j in s:
        if j == "1":
            on += 1

    if on != (N+1)//2:
        continue

    q = []
    q2 = []

    for i in range(N):
        if s[i] == "1":
            if i % 2 == 0:
                q.append([A[i],i])
            else:
                q.append([B[i],i])
        else:
            if i % 2 != 0:
                q2.append([A[i],i])
            else:
                q2.append([B[i],i])           

    q.sort()
    q2.sort()
    q2.append([float("inf"),0])
    #print (q,q2)

    flag = True
    nmax = 0

    for i in range((N+1)//2):


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

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

    if flag:
        r = []
        for i in range((N+1)//2):
            r.append(q[i][1])
            r.append(q2[i][1])

        #print (r)

        now = 0
        z = [i for i in range(N)]
        for i in range(N):
            for j in range(len(z)):
                if z[j] == r[i]:
                    now += j
                    del z[j]
                    break
            #print (z,now)
        ans = min(now,ans)

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

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

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

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

def main():
    def ng():
        px=-1
        for i in range(n):
            if i % 2:
                x = xx1[i // 2][1]
            else:
                x = xx0[i // 2][0]
            if x<px:return True
            px=x
        return False

    def change(ans):
        res=0
        bit=BitSum(n)
        for i,k in enumerate(kk):
            res+=i-bit.sum(k)
            if res>ans:return ans
            bit.add(k,1)
        return res

    n = II()
    aa = LI()
    bb = LI()
    ab = []
    for i, (a, b) in enumerate(zip(aa, bb)):
        if i % 2:
            ab.append([b, a, i])
        else:
            ab.append([a, b, i])
    ans=1000
    for odd in combinations(range(n), n // 2):
        isodd = [False] * n
        xx0 = []
        xx1 = []
        for i in odd:
            xx1.append(ab[i])
            isodd[i] = True
        for i in range(n):
            if isodd[i]: continue
            xx0.append(ab[i])
        xx0.sort(key=lambda x: (x[0],x[2]))
        xx1.sort(key=lambda x: (x[1],x[2]))
        #print(xx0)
        #print(xx1)
        if ng():continue
        kk=[]
        for [_,_,i0],[_,_,i1] in zip(xx0,xx1):
            kk+=[i0,i1]
        if n%2:kk+=[xx0[-1][2]]
        #print(kk)
        ans=change(ans)
        #print(ans,xx0,xx1)
    if ans==1000:print(-1)
    else:print(ans)

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from itertools import combinations
    from operator import itemgetter
    input = sys.stdin.readline

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

    even = []
    odd = []
    for i in range(N):
        if i%2:
            odd.append(A[i])
            even.append(B[i])
        else:
            even.append(A[i])
            odd.append(B[i])

    L = list(range(N))
    ans = 10**9
    for v in combinations(L, N//2):
        ok = 1
        tmp = []
        tmp_odd = []
        tmp_even = []
        for i in range(N):
            if i in v:
                tmp.append(odd[i] * 100)
                tmp_odd.append((odd[i], i))
            else:
                tmp.append(even[i] * 100)
                tmp_even.append((even[i], i))

        tmp_odd.sort(key=itemgetter(0))
        tmp_even.sort(key=itemgetter(0))

        tmp_check = []
        p = [0] * N
        for i in range(N):
            if i%2:
                tmp_check.append(tmp_odd[i//2][0])
                p[tmp_odd[i//2][1]] = i
            else:
                tmp_check.append(tmp_even[i // 2][0])
                p[tmp_even[i // 2][1]] = i
        for i in range(N-1):
            if tmp_check[i] > tmp_check[i+1]:
                ok = 0
                # print(v, tmp_check, odd, even)
                break
        if not ok:
            continue

        for i in range(N):
            tmp[i] += p[i]

        ans_new = 0
        for i in range(N):
            for j in range(i+1, N):
                if tmp[i] > tmp[j]:
                    ans_new += 1
        # print(v, tmp, ans_new, odd, even)
        ans = min(ans, ans_new)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

odds = []
evens = []
for i in range(n):
    if i%2 == 0:
        odds.append([a[i],i])
        evens.append([b[i],i])
    else:
        odds.append([b[i],i])
        evens.append([a[i],i])

odds = sorted(odds)
evens = sorted(evens)
#print("odss =",odds)
#print("evens =",evens)

inds = [i for i in range(n)]

ans = 10000000000
exist = 0
#print("開始")
half = (n-1)//2 + 1
for v in  itertools.combinations(inds,half):
    #print("start")

    #print(v)
    real_v = [odds[i][1] for i in v]
    #vに入らなかった方を生成する
    real_nokori = []

    for i in range(n):
        if not (evens[i][1] in real_v):
            real_nokori.append(evens[i][1])
    
    nokori = []
    for i in range(n):
        if evens[i][1] in real_nokori:
            nokori.append(i)

    #print(v,nokori)


    moge = 1
    if n%2 == 0:
        for i in range(half):
                if evens[nokori[i]][0] < odds[v[i]][0]:
                    moge = 0
    else:
        for i in range(n-half):
                if evens[nokori[i]][0] < odds[v[i]][0]:
                    moge = 0

    for i in range(half-1):
        if evens[nokori[i]][0] > odds[v[i+1]][0]:
            moge = 0

    if moge != 1:
        continue
    else:
        exist = 1

    tar = []
    for i in range(n):
        if i%2 == 0:
            tar.append(real_v[i//2])
        else:
            tar.append(real_nokori[(i-1)//2])
    dist = 0
    for i in range(n):
        for mo in range(i+1,n):
            if tar[mo] < tar[i]:
                dist += 1
    if dist < ans:
        ans = dist
if exist:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

INF = N *100
ans = INF
for i in range(2**N):
    C = [((a,j,0) if (i>>j)&1 else (b,j,1)) for j,a,b in zip(range(N),A,B)]
    P = sum(p for c,j,p in C)
    if P%2: continue
    E = sum(p for c,j,p in C[::2])
    O = sum(p for c,j,p in C[1::2])
    if E!=O: continue
    C0 = []
    C1 = []
    for c,j,p in C:
        if (p+j)%2:
            C1.append((c,j,p))
        else:
            C0.append((c,j,p))
    C0.sort()
    C1.sort()
    D = []
    E = []
    for c0,c1 in zip(C0,C1):
        E.append(c0[0])
        E.append(c1[0])
        D.append(c0[1])
        D.append(c1[1])
    if N%2:
        D.append(C0[-1][1])
        E.append(C0[-1][0])
    contFlg = False
    for e,e2 in zip(E[:-1],E[1:]):
        if e>e2:
            contFlg = True
            break
    if contFlg: continue
    tmp = 0
    for i,d in enumerate(D):
        for j,d2 in enumerate(D[:i]):
            if d2 > d: tmp += 1
    ans = min(ans,tmp)
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import sys
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a2=list()
b2=list()

if n==1:
    print(0)
    sys.exit()
    
for i in range(n):
    if i%2:
        b2.append(a[i])
        a2.append(b[i])
    else:
        a2.append(a[i])
        b2.append(b[i])

ans=10**9
for idx in combinations(range(0,n), (n+1)//2):
    a3=list()
    b3=list()
    flag=True
    for i in range(n):
        if i in idx:
            a3.append([a2[i], i])
        else:
            b3.append([b2[i], i])
    a3.sort(key=lambda x:x[0])
    b3.sort(key=lambda x:x[0])

    for i in range(len(b3)-1):
        if a3[i][0]>b3[i][0] or a3[i+1][0]<b3[i][0]:
            flag=False
    if len(a3)>len(b3):
        if a3[-1][0]<b3[-1][0] or a3[-2][0]>b3[-1][0]:
            flag=False
    elif a3[-1][0]>b3[-1][0]:
        flag=False

    if flag:
        ansidx = list()
        for i in range(len(b3)):
            ansidx.append(a3[i][1])
            ansidx.append(b3[i][1])
        if len(a3)>len(b3):
            ansidx.append(a3[-1][1])

        swap=0
        for i in range(n):
            for j in range(i,n):
                if ansidx[i]>ansidx[j]:
                    swap+=1
        ans= min(ans, swap)

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

Submission status: Accepted

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

o=N//2
e=N-o

import itertools
E=[]
O=[]
for i in range(N):
    if i%2==0:
        E.append(i)
    else:
        O.append(i)
ANS=10000

def mergecount(Z):
    cnt1 = 0
    z = len(Z)
    if z>1:
        A1 = Z[:z>>1]
        A2 = Z[z>>1:]
        cnt1 += mergecount(A1)
        cnt1 += mergecount(A2)
        i1=0
        i2=0
        for i in range(z):
            if i2 == len(A2):
                Z[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                Z[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                Z[i] = A1[i1]
                i1 += 1
            else:
                Z[i] = A2[i2]
                i2 += 1
                cnt1 += z//2 - i1
    return cnt1

for i in range(o+1):
    X=list(itertools.combinations(E,i))
    Y=list(itertools.combinations(O,i))
    for j in range(len(X)):
        for k in range(len(Y)):
            ev=[]
            od=[]
            for n in range(N):
                if n%2==0:
                    if n in X[j]:
                        od.append([B[n],n])
                    else:
                        ev.append([A[n],n])
                else:
                    if n in Y[k]:
                        ev.append([B[n],n])
                    else:
                        od.append([A[n],n])
            ev.sort()
            od.sort()
            #print(ev,od)
            Z=[]
            Num=0
            F=0
            for x in range(N):
                if x%2==0:
                    if Num>ev[x//2][0]:
                        F=1
                        break
                    else:
                        Num=ev[x//2][0]
                        Z.append(ev[x//2][1])
                else:
                    if Num>od[x//2][0]:
                        F=1
                        break
                    else:
                        Num=od[x//2][0]
                        Z.append(od[x//2][1])
            if F==0:
                #print(Z)
                tcnt=mergecount(Z)
            if F==0 and tcnt<ANS:
                ANS=tcnt
                
if ANS==10000:
    print(-1)
else:
    print(ANS)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import itertools

#Binary Indexed Tree
#O(logN)でtに1点加算、t以下の合計を得る

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

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

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

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	#入力処理
	N = int(input())
	A = getlist()
	B = getlist()
	omote = []
	ura = []
	for i in range(N):
		if i % 2 == 0:
			omote.append([A[i], i])
			ura.append([B[i], i])
		else:
			omote.append([B[i], i])
			ura.append([A[i], i])

	#半分全列挙
	seq = [i for i in range(N)]
	alllist = list(itertools.combinations(seq, int((N + 1) // 2)))
	M = len(alllist)
	#print(alllist)
	ans = float("inf")
	for i in range(M):
		lis = alllist[i]
		USE = [0] * N
		for j in lis:
			USE[j] = 1 #1:表 0:裏
		X = []
		Y = []
		for j in range(N):
			if USE[j] == 1:
				X.append(omote[j])
			else:
				Y.append(ura[j])
		X = sorted(X)
		Y = sorted(Y)
		sequence = []
		for j in range(N):
			if j % 2 == 0:
				sequence.append(X[int(j // 2)])
			else:
				sequence.append(Y[int(j // 2)])
		#print(sequence)
		judge = "Yes"
		for j in range(N - 1):
			if sequence[j][0] > sequence[j + 1][0]:
				judge = "No"
				break
		if judge == "Yes":
			bit = []
			for j in range(N):
				bit.append(sequence[j][1] + 1)
			# print(bit)
			val = 0
			calc = BIT(50)
			for j in range(N):
				calc.add(bit[j], 1)
				val += j + 1 - calc.sum(bit[j])
			# print(val)
			ans = min(ans, val)

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


# N = int(input())
# M = int(input())
# A = getlist()

# bit = BIT(M)
# for i in range(N):
# 	bit.add(A[i], 1)
# 	ans += i + 1 - bit.sum(A[i])

# print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():

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

    if all(a[0] == a[i] for i in range(n)):
        print(0)
        exit()

    pre = [1<<i for i in range(n)]
    bitcnt = [0]*(1<<n)
    bitcnt[1] = 1
    for i in range(1<<(n-1)):
        bitcnt[2*i] = bitcnt[i]
        bitcnt[2*i+1] = bitcnt[i]+1

    DP = [defaultdict(lambda : float("inf")) for i in range(n)]

    for i in range(n):
        DP[i][1<<i] = 0
    s = defaultdict(lambda : float("inf"))
    for i in range(n-1):
        nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
        for j in range(n):
            last = a[j] if (i-j)%2 == 0 else b[j]
            for state, cost in DP[j].items():
                for to in range(n):
                    if state>>to&1:
                        continue
                    nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                    if last > nlast:
                        continue
                    nstate = state|pre[to]
                    ncost = cost
                    ncost += bitcnt[state>>to]
                    if s[(nstate, nlast)] <= ncost:
                        continue
                    s[(nstate, nlast)] = ncost
                    if nxt[to][nstate] > ncost:
                        nxt[to][nstate] = ncost
        DP = nxt
    mask = (1<<n)-1
    ans = float("inf")
    for i in range(n):
        ans = min(ans, DP[i][mask])
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    dg = 20

    pp = 20

    dp = [10**5]*(10**7)

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s*pp+i] = i
        new.add(s*dg+i)

    for k in range(n-1):
        tank = set([])
        if len(new) == 0:
            break
        for popelt in new:
            s,idx = popelt//dg,popelt%dg
            if (k-idx)%2 == 0:
                fr = a[idx]
            else:
                fr = b[idx]
            cnt = 0
            for j in range(n):
                if (s>>j)&1 == 0:
                    if (j-k)%2 == 1:
                        val = a[j]
                    else:
                        val = b[j]
                    if val >= fr and dp[(s+(1<<j))*pp+j] > dp[s*pp+idx]+j-cnt:
                        dp[(s+(1<<j))*pp+j] = dp[s*pp+idx]+j-cnt
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
        new = tank
    
    res = 10**5
    s = (2**n-1)*pp
    for i in range(n):
        if res > dp[s+i]:
            res = dp[s+i]
    if res == 10**5:
        print(-1)
    else:
        print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

L = [[0]*2 for _ in range(N)]

for i in range(N):
    L[i][i%2] = A[i]
    L[i][(i+1)%2] = B[i]

P = [int(i) for i in range(N)]

ans = 10**10
import itertools
for C in itertools.combinations(P, (N+1)//2):
    C = list(C)
    used = [0]*N
    for i in C:
        used[i] = 1
    B_temp = []
    for i in range(N):
        if used[i] == 0:
            B_temp.append((L[i][1], i))

    temp = [0]*N
    check = [0]*N
    B_temp.sort()
    for i in range(len(C)):
        C[i] = (L[C[i]][0], C[i])
    C.sort()
    j = 0
    k = 0
    for i in range(N):
        if i%2 == 0:
            temp[i] = C[j][1]
            check[i] = C[j][0]
            j += 1
        else:
            temp[i] = B_temp[k][1]
            check[i] = B_temp[k][0]
            k += 1
    if check != sorted(check):
        continue

    cnt = 0
    for i in reversed(range(N)):
        for j in range(i):
            if temp[j] > temp[j + 1]:
                temp[j], temp[j + 1] = temp[j + 1], temp[j]
                cnt += 1

    ans = min(ans, cnt)

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=10**9
def bubble_sort(arr):
    change = True
    num=0
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
                num+=1
    return num
for i in range(2**n):
    even=[]
    odd=[]
    for j in range(n):
        x=(i>>j)%2
        if j%2==0:
            if x==0:
                even.append((a[j],j))
            else:
                odd.append((b[j],j))
        else:
            if x==0:
                odd.append((a[j],j))
            else:
                even.append((b[j],j))
    if len(odd)!=n//2:
        continue
    even.sort()
    odd.sort()
    check=True
    order=[]
    new=[]
    for j in range(n//2):
        order.append(even[j][1])
        order.append(odd[j][1])
        new.append(even[j][0])
        new.append(odd[j][0])
    if n%2!=0:
        new.append(even[-1][0])
        order.append(even[-1][1])
    for j in range(n-1):
        if new[j]>new[j+1]:
            check=False
    if not check:
        continue
    x=bubble_sort(order)
    ans=min(ans,x)
if ans==10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
lst=[]
for i in range(2**N):
    h=[[],[]]
    for j in range(N):
        if (i>>j)&1==1:
            h[(j+1)%2].append([B[j],j])
        else:
            h[j%2].append([A[j],j])
    if len(h[1])==N//2:
        lst.append(h)
lsls=[]
for h in lst:
    h[0].sort()
    h[1].sort()
    cnt=h[0][0][1]
    for i in range(N-1):
        if h[i%2][i//2][0]>h[(i+1)%2][(i+1)//2][0]:
            break
    else:
        hhh=[]
        for i in range(N):
            hhh.append(h[i%2][i//2][1])
        lsls.append(hhh)
inf=float("inf")
ans=inf
if lsls:
    for h in lsls:
        flag=[0]*N
        cnt=0
        for u in h:
            flag[u]=1
            cnt+=sum(flag[u+1:])
        ans=min(ans,cnt)
if ans==inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
al = list(map(int,input().split()))
bl = list(map(int,input().split()))

def bubble_sort(lst):
    a = 0
    for i in range(len(lst)-1):
        for j in range(len(lst)-1, i, -1):
            if lst[j-1] > lst[j]:
                tmp = lst[j]
                lst[j] = lst[j-1]
                lst[j-1] = tmp
                a += 1
    return a

anss = float("inf")
for i in range(2 ** n):
    bits = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            bits[j] = 1
    even_odd = [[], []]
    for idx, bit in enumerate(bits):
        if bit == 0:
            even_odd[(idx + bit) % 2].append((al[idx], idx))
        else:
            even_odd[(idx + bit) % 2].append((bl[idx], idx))
    if len(even_odd[0]) - len(even_odd[1]) != n % 2:
        continue
    aal = sorted(even_odd[0])
    bbl = sorted(even_odd[1])
    goto = []
    now = 0
    for k in range(n):
        if k % 2 == 0:
            tmp, idx = aal.pop(0)
            if now <= tmp:
                goto+= [idx]
                now = tmp
            else:
                break
        else:
            tmp, idx = bbl.pop(0)
            if now <= tmp:
                goto+= [idx]
                now = tmp
            else:
                break
    else:
        ans = bubble_sort(goto)
        anss = min(anss, ans)

if anss == float('inf'):
    print(-1)
else:
    print(anss)

Submission status: Accepted

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)
    Pi = [None]*N
    for i in range(N):
        Pi[P[i]] = i
    for i in range(N):
        p = Pi[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**9+7
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[0] > o[0] for e, o in zip(even, odd)) or any(e[0] < o[0] 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)]
    ans = min(ans, count(perm))
print(ans if ans < inf else -1)

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

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

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


from operator import itemgetter
from collections import deque

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 10**18


for bit_state in range(1 << n):
    pattern = [[] for i in range(2)]
    for i in range(n):
        if bit_state & (1 << i) and i % 2 == 0:
            pattern[0].append(a[i]*100 + i)
        elif bit_state & (1 << i) and i % 2 == 1:
            pattern[1].append(a[i]*100 + i)
        elif i % 2 == 0:
            pattern[1].append(b[i]*100 + i)
        else:
            pattern[0].append(b[i]*100 + i)

    if len(pattern[0]) == len(pattern[1]) or len(pattern[0]) - 1 == len(pattern[1]):
        for i in range(2):
            pattern[i] = sorted(pattern[i])
        bit = BIT(n)
        ans_tmp = 0
        prev_num = 10**8
        for i in range(n)[::-1]:
            pal = i % 2
            num = pattern[pal].pop()
            ind = num % 100
            num = num // 100
            if prev_num < num:
                break
            prev_num = num
            bit.add(ind, 1)
            ans_tmp += bit.get_sum(0, ind)
        else:
            ans = min(ans, ans_tmp)

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

Submission status: Accepted

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

#n = int(input)
#h,w = [int(i) for i in readline().split()]
#n,k,s = [int(i) for i in read().split()]

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

N = 1<<n
ans = INF = 10**9
for mask in range(N):
    bucket = [[] for _ in range(50)]
    for i in range(n):
        bucket[a[i] if mask&(1<<i) else b[i]].append(i)
    
    cnt = 0
    res = []
    #print(bucket)
    #if mask == 3: print(bucket[:5])
    for bi in bucket:
        if not bi: continue
        l = len(bi)
        o = [i for i in bi if ((mask>>i)^i)&1==0]
        e = [i for i in bi if ((mask>>i)^i)&1==1]
        odd = len(o)
        even = len(e)
        #if mask == 3: print(cnt,bi,o,e)
        if l%2 == 0:
            if odd != even: break
        else:
            if cnt%2==0:
                if even != odd+1: break
            else:
                if odd != even+1: break
        
        #偶奇を突破したら
        for i in range(l):
            res.append(e[i//2] if (i+cnt)%2==0 else o[i//2])
        cnt += l
        
        
    else: #うまくいったら
        num = 0
        for i in range(n):
            for j in range(i+1,n):
                if res[i] > res[j]: num += 1
        #print(mask,num,res)
        ans = min(ans,num)                

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