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:
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
nn=2**n
ans=float("inf")
for i in range(nn):
  C=[]
  for j in range(n):
    if i&(1<<j)==0:
      C.append([A[j],j,0])
    else:
      C.append([B[j],j,1])

  C.sort(key=lambda x:(x[0],x[1]))

  chk=True
  for ii in range(n):
    if (C[ii][1]-C[ii][2]-ii)%2==0:
        continue
    else:
      chk=False
      break
  if chk:
    ct=0
    for i1 in range(n):
      for i2 in range(i1+1,n):
        if C[i1][1]>C[i2][1]:
          ct+=1
    ans=min(ans,ct)
print(-1 if ans==float("inf") else ans)

Submission status: Wrong Answer

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

ans = 10**9

for i in range(2 ** n):
    j = 1
    c = []
    count = 0
    for k in range(n):
        if (i & j) == 0:
            c.append([a[k], k, 0, 0])
        else:
            c.append([b[k], k, 1, 0])
            count += 1
        j *= 2
    if count % 2 != 0:
        continue

    for _ in range(n - 1):
        for j in range(n - 1):
            if c[j] > c[j + 1]:
                c[j][-1] += 1
                c[j + 1][-1] += 1
                c[j], c[j + 1] = c[j + 1], c[j]

    flag = True
    for j in range(n):
        if c[j][-1] % 2 != c[j][2]:
            if j == n - 1 or c[j][0] != c[j + 1][0]:
                flag = False
            else:
                c[j][-1] += 1
                c[j + 1][-1] += 1
                c[j], c[j + 1] = c[j + 1], c[j]

    if flag:
        cost = 0
        for j in c:
            cost += j[-1]
        ans = min(ans, cost//2)

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

Submission status: Wrong Answer

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



from collections import defaultdict

ans = 10**27

for i in range(2**N):
    num = i
    ab_list = []
    sig_list = []
    for j in range(N):
        if num%2==0:
            ab_list.append(A[j])
            sig_list.append(0)
        else:
            ab_list.append(B[j])
            sig_list.append(1)
        num//=2
    
    goal_list = sorted(ab_list)
    prev = goal_list[0]
    dl = defaultdict(int)
    dr = defaultdict(int)
    dl[prev] = 0
    for j in range(1,N):
        if goal_list[j]>prev:
            dr[prev] = j-1
            prev = goal_list[j]
            dl[prev] = j
    dr[prev] = N-1
    dcounto = defaultdict(int)
    dcounte = defaultdict(int)
    score = 0
    flag=True
    #print(dl,dr)
    for j in range(N):
        par = (dl[ab_list[j]]-j+sig_list[j])%2
        if par==0:
            target = dl[ab_list[j]]+dcounte[ab_list[j]]*2
            dcounte[ab_list[j]]+=1
        else:
            target = dl[ab_list[j]]+dcounto[ab_list[j]]*2+1
            dcounto[ab_list[j]]+=1
        if target>dr[ab_list[j]]:
            score=-1
            flag=False
            break
        #print(target)
        score+=abs(target-j)
    if flag:
        #print(score,ab_list,goal_list,sig_list)
        ans=min(ans,score//2)

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

Submission status: Wrong Answer

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

def mergecnt(a):
    cnt = 0
    n = len(a)
    if n > 1:
        b = a[:n//2]
        c = a[n//2:]
        cnt += mergecnt(b)
        cnt += mergecnt(c)
        j = 0
        k = 0
        for i in range(n):
            if k == len(c):
                a[i] = b[j]
                j += 1
            elif j == len(b):
                a[i] = c[k]
                k += 1
            elif b[j] <= c[k]:
                a[i] = b[j]
                j += 1
            else:
                a[i] = c[k]
                k += 1
                cnt += n // 2 - j
    return cnt

Ac = mergecnt(A)
Bc = mergecnt(B)

if Ac % 2 == 0 and Bc % 2 == 1:
    print(min(Ac, Bc))
elif Ac % 2 == 1 and Bc % 2 == 0:
    print(-1)
elif Ac % 2 == 0 and Bc % 2 == 0:
    print(Ac)
else:
    print(Bc)

Submission status: Wrong Answer

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

c = []
for i in range(n):
    c.append((a[i],b[i]))

import itertools

l = [i for i in range(n)]
ans = 10**9


for v in itertools.permutations(l,n):
    tmp = 0
    cnt = 0
    for i in range(n):
        if tmp <= c[v[i]][(i-v[i])%2]:
            tmp = c[v[i]][(i-v[i])%2]
            cnt += 1
        else:
            break
    if cnt == n:
        kaisu = 0
        visited = [False]*n
        ttt = 0
        visited[ttt] = True
        while True:
            if not visited[v[ttt]]:
                kaisu += 1
                visited[v[ttt]] = True
                ttt = v[ttt]
            else:
                check = False
                for i in range(n):
                    if not visited[i]:
                        check = True
                        ttt = i
                        visited[ttt] = True
                if not check:
                    break
        ans = min(ans, kaisu)

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

Submission status: Wrong Answer

Solution code:
from itertools import *
def count_inversion(sequence):
    return sum(sum(m<n for m in sequence[i+1:]) for i,n in enumerate(sequence))

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

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

up.sort()
l = set([i for i in range(n)])

ans = 100
for u in combinations(up, (n+1)//2):
    index = []
    value = []
    for val, ind in u:
        index.append(ind)
        value.append(val)

    d_index = l - set(index)
    d = []
    for i in d_index:
        d.append(down[i])
    d.sort()
    value.append(100)
    flag = 1
    for i in range(len(d)):
        if not value[i] <= d[i][0] <= value[i+1]:
            flag = 0
            break
    if flag == 0:
        continue

    for i in range(len(d)):
        index.insert(2*i+1, d[i][1])

    ans = min(ans, count_inversion(index))



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

Submission status: Wrong Answer

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

def main():
    pti = time.time()
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    dg = 10**10

    dp = [[10**5]*n for i in range(2**n)]

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s][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:
                        dp[s+(1<<j)][j] = min(dp[s+(1<<j)][j],dp[s][idx]+j-cnt)
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
        if time.time()-pti > 1.5:
            print(n*(n-1)//2)
            return    
        new = tank
    
    res = min(dp[2**n-1])

    if res == 10**5:
        print(-1)
    else:
        print(res)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
for i in range(10000):
    if A == sorted(A):
        print(ans)
        quit()
    for i in range(N-1):
        a = A[i]
        ai = A[i+1]
        b = B[i]
        bi = B[i+1]
        if b > bi:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
            continue
        elif a > ai:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
            continue
print(-1)

Submission status: Wrong Answer

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

ac = 0
bc = 0
for h in range(1000):
  for i in range(n-1):
      flag = True
      if a[i+1] < a[i]:
        if b[i] < b[i+1] and i != 0:
          a[i],a[i-1] = b[i-1],b[i]
          ac += 1
          #print(a)
        else:
          a[i+1],a[i] = b[i],b[i+1]
          ac += 1
          #print(a)
          
          
for i in range(n-1):
  if a[i] > a[i+1]:
    print(-1)
    sys.exit()
print(ac)

Submission status: Wrong Answer

Solution code:
n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
ab = []

for i in range(n):
    ab.append((aa[i], bb[i]))

min_step = 10**9
for i in range(2**n):
    bin_str = "{:020b}".format(i)[20-n:]
    bins = list(map(int, list(bin_str)))
    vals = [(ab[i][bins[i]], bins[i], i) for i in range(n)]
    step_sum = 0
    illegal = False
    for new_ind, (val, ht, ind) in enumerate(sorted(vals)):
        step = abs(new_ind - ind)
        if (step % 2 == 0 and ht == 1) or (step % 2 == 1 and ht == 0):
            illegal = True
            break
        step_sum += step
    step_sum //= 2
    if not illegal:
        min_step = min(min_step, step_sum)
if min_step == 10**9:
    print(-1)
else:
    print(min_step)

Submission status: Wrong Answer

Solution code:
n = int(input())
red = list(map(int,input().split()))
blue = list(map(int,input().split()))
ans = 10 ** 5
for i in range(2 ** n):
    s = format(i,"b").zfill(n)
    num = [[red[j],j] if s[j] == "0" else [blue[j],j+1,j] for j in range(n)]
    num.sort()
    key = 1
    nu = 0
    for h in range(n):
        nu += abs(num[h][-1]-h)
        if (num[h][1]-h) % 2 != 0:
            key = 0
    if key:
        ans = min(ans,nu//2)
if ans == 10 ** 5:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import *
def count_inversion(sequence):
    return sum(sum(m<n for m in sequence[i+1:]) for i,n in enumerate(sequence))

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

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

up.sort()
l = set([i for i in range(n)])

ans = 100
for u in combinations(up, 3):
    index = []
    value = []
    for val, ind in u:
        index.append(ind)
        value.append(val)

    d_index = l - set(index)
    d = []
    for i in d_index:
        d.append(down[i])
    d.sort()
    value.append(100)
    flag = 1
    for i in range(len(d)):
        if not value[i] <= d[i][0] <= value[i+1]:
            flag = 0
            break
    if flag == 0:
        continue

    for i in range(len(d)):
        index.insert(2*i+1, d[i][1])

    ans = min(ans, count_inversion(index))



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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = float("inf")
for i in range(2**n):
  L = []
  G = []
  for j in range(n):
    if i>>j & 1:
      L.append(B[j])
      G.append(1)
    else:
      L.append(A[j])
      G.append(0)
  C = [0]*n
  cnt = 0
  for s in range(n-1):
    for t in range(s+1, n):
      if L[s] > L[t]:
        C[s] ^= 1
        C[t] ^= 1
        cnt += 1
  D = sorted((j, i) for i, j in enumerate(L))
  L, M = zip(*D)
  L = list(L)
  C = [C[i] for i in M]
  G = [G[i] for i in M]
  L.append("#")
  K = [0]
  for q in range(n):
    if L[q] != L[q+1]:
      K.append(q+1)
  for e in range(len(K)-1):
    c = 0
    for b in range(K[e], K[e+1]-1):
      if C[b] ^ G[b]:
        G[b+1] ^= 1
        c += 1
    if G[K[e+1]-1] != C[K[e+1]-1]:
      cnt = float("inf")
      break
    else:
      cnt += c
  ans = min(ans, cnt)
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
import time
import copy
start = time.time()
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
X = []
for i in range(N):
    X.append((A[i],B[i]))
ans = -1
Q = [(0,X)]
while Q:
    if time.time()-start>1.5:break
    q = heappop(Q)
    A = [e[0] for e in q[1]]
    if A==sorted(A):
        ans=max(q[0],ans)
        break
    for i in range(N-1):
        Y = q[1][:]
        Y[i] = (q[1][i+1][1],q[1][i+1][0])
        Y[i+1] = (q[1][i][1],q[1][i][0])
        heappush(Q,(q[0]+1,Y))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 10**9
for i in range(2**N):
    tmp = []
    count = 0
    for j in range(N):
        if (i >> j) % 2 == 1:
            tmp.append((A[j], j))
            count += 1
        else:
            tmp.append((B[j], j))

    tmp.sort()
    tmp_ans = 0
    flag = True
    for j in range(N):
        if abs(tmp[j][1] - j) % 2 == 0:
            if tmp[j][0] != A[tmp[j][1]]:
                flag = False
                break
        else:
            if tmp[j][0] != B[tmp[j][1]]:
                flag = False
                break
        tmp_ans = max(tmp_ans, abs(tmp[j][1] - j))
    if flag:
        ans = min(tmp_ans, ans)
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
red = list(map(int,input().split()))
blue = list(map(int,input().split()))
ans = 10 ** 5
for i in range(2 ** n):
    s = format(i,"b").zfill(n)
    num = [[red[j],j] if s[j] == "0" else [blue[j],j+1] for j in range(n)]
    num.sort()
    key = 1
    for h in range(n):
        if (num[h][1]-h) % 2 != 0:
            key = 0
    if key:
        ans = min(ans,max(s.count("1")-1,0))
if ans == 10 ** 5:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

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])
    ans = 0
    now = 0
    for k in range(n):
        if k % 2 == 0:
            tmp, idx = aal.pop(0)
            if now <= tmp:
                ans += abs(k-idx)
                now = tmp
            else:
                break
        else:
            tmp, idx = bbl.pop(0)
            if now <= tmp:
                ans += abs(k-idx)
                now = tmp
            else:
                break
    else:
        anss = min(anss, ans)

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

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self, n):
        self.N = n
        self.n = 1<<n.bit_length()
        self.data = [0] * (self.n + 1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 10**10
for s in range(1<<N):
    C = []
    c_to_i = [-1]*(51)
    for i in range(N):
        if s&(1<<i):
            C.append((B[i], i))
        else:
            C.append((A[i], i))
    C.sort()
    flag = True
    for j, c in enumerate(C):
        c, i = c
        if ((s>>i)&1)^((j-i)%2):
            flag = False
            break
    if flag:
        Bit = BIT(N)
        res = 0
        for c, i in C[::-1]:
            Bit.add(i+1, 1)
            res+=Bit.sum(i)
        ans = min(ans, res)
print(ans if ans<10**10 else -1)

Submission status: Wrong Answer

Solution code:

def minSwaps(arr): 
    n = len(arr) 
    arrpos = list(enumerate(arr))
    arrpos.sort(key = lambda it:it[1]) 
    vis = {k:False for k in range(n)} 
      
    ans = 0
    for i in range(n): 
        if vis[i] or arrpos[i][0] == i: 
            continue
        cycle_size = 0
        j = i 
        while not vis[j]: 
            vis[j] = True
            j = arrpos[j][0] 
            cycle_size += 1
        if cycle_size > 0: 
            ans += (cycle_size - 1) 
    return ans 


from itertools import combinations, zip_longest

N = int(input())

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

cards = [(a,b) if i % 2 == 0 else (b,a) for i,(a,b) in enumerate(zip(A,B))]

best = float('inf')

for odd_indices in combinations(range(N), N//2):
    odds = sorted((cards[i][1], i) for i in odd_indices)
    evens = sorted((card[0], i) for i,card in enumerate(cards) if i not in odd_indices)


    union = []
    for e,o in zip_longest(evens,odds):
        union.append(e)
        if o is not None:
            union.append(o)
    if all(a <= b for (a,_),(b,_) in zip(union,union[1:])):
        indices = [i for _,i in union]
        best = min(best, minSwaps(indices))

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

Submission status: Wrong Answer

Solution code:
import sys,time
from collections import deque
input = sys.stdin.readline

def main():

    pti = time.time()

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

    dg = 10**10

    dp = [[10**5]*n for i in range(2**n)]

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

    for k in range(n-1):
        tank = set([])
        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:
                        dp[s+(1<<j)][j] = min(dp[s+(1<<j)][j],dp[s][idx]+j-cnt)
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
            
        new = tank
        if time.time()-pti > 1.6:
            print(n*(n-1)//2)
            return
    
    res = min(dp[2**n-1])

    if res == 10**5:
        print(-1)
    else:
        print(res)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
import time
import copy
start = time.time()
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
X = []
for i in range(N):
    X.append((A[i],B[i]))
ans = -1
Q = [(0,X)]
while Q:
    if time.time()-start>1.3:break
    q = heappop(Q)
    A = [e[0] for e in q[1]]
    if A==sorted(A):
        ans=max(q[0],ans)
        break
    for i in range(N-1):
        Y = q[1][:]
        Y[i] = (q[1][i+1][1],q[1][i+1][0])
        Y[i+1] = (q[1][i][1],q[1][i][0])
        heappush(Q,(q[0]+1,Y))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
nn=2**n
ans=float("inf")
for i in range(nn):
  C=[]
  for j in range(n):
    if i&(1<<j)==0:
      C.append([A[j],j,0])
    else:
      C.append([B[j],j,1])
    #j桁目が０ならAから１ならBからとる
      
    #ソートする
  C.sort(key=lambda x:(x[0],x[1]))
    
  #前から見ていき、次のチェックをする
  #偶数番目はAの偶数番目またはBの木数番目かどうか
  #木数番目はその逆
  chk=True
  for ii in range(n):
    if ii%2==0:
      if C[ii][1]%2==C[ii][2]:
        continue
      else:
        chk=False
    else:
      if C[ii][1]%2==C[ii][2]:
        chk=False
      else:
        continue
  #すべてクリアしたものがあれば、転倒数をカウントする、最小値を更新
  if chk:
    ct=0
    for i1 in range(n):
      for i2 in range(i1+1,n):
        if C[i1][1]>C[i2][1]:
          ct+=1
    ans=min(ans,ct)
print(-1 if ans==float("inf") else ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = float("inf")
for i in range(2**n):
  L = []
  G = []
  for j in range(n):
    if i>>j & 1:
      L.append(B[j])
      G.append(1)
    else:
      L.append(A[j])
      G.append(0)
  C = [0]*n
  cnt = 0
  for s in range(n-1):
    for t in range(s+1, n):
      if L[s] > L[t]:
        C[s] ^= 1
        C[t] ^= 1
        cnt += 1
  D = sorted((j, i, C[i], G[i]) for i, j in enumerate(L))
  L, M, C, G = zip(*D)
  L = list(L)
  G = list(G)
  L.append("#")
  K = [0]
  for q in range(n):
    if L[q] != L[q+1]:
      K.append(q+1)
  for e in range(len(K)-1):
    c = 0
    for b in range(K[e], K[e+1]-1):
      if C[b] ^ G[b]:
        G[b+1] ^= 1
        c += 1
    if G[K[e+1]-1] != C[K[e+1]-1]:
      cnt = float("inf")
      break
    else:
      cnt += c
  ans = min(ans, cnt)
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

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

def count(P):
    res = 0
    T = BIT(N)
    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 > o for e, o in zip(even, odd)) or any(e < o for e, o in zip(even[1:], odd)):
        continue
    perm = [even[i//2][1] if not i&1 else odd[i//2][1] for i in range(N)]

    ans = min(ans, count(perm))
print(ans if ans < inf else -1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
for i in range(1000):
    if A == sorted(A):
        print(ans)
        quit()
    for i in range(N-1):
        a = A[i]
        ai = A[i+1]
        b = B[i]
        bi = B[i+1]
        if b > bi:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
            continue
        elif a > ai:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
            continue
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
red = list(map(int,input().split()))
blue = list(map(int,input().split()))
ans = 10 ** 5
for i in range(2 ** n):
    s = format(i,"b").zfill(n)
    num = [[red[j],j] if s[j] == "0" else [blue[j],j+1] for j in range(n)]
    num.sort()
    key = 1
    for h in range(n):
        if (num[h][1]-h) % 2 != 0:
            key = 0
    if key:
        ans = min(ans,max(s.count("1")-1,0))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

# 2**18 == 262144
N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))

a = math.factorial(18)
b = math.factorial(9)

# 18C9 < 50000
# どれを偶数番目にするか決まれば回数も分かる
ans = INF
for evens_i in itertools.combinations(range(N), r=(N + 1) // 2):
    is_even = [False] * N
    for i in evens_i:
        is_even[i] = True
    evens = []
    odds = []
    for i, even in enumerate(is_even):
        if even:
            evens.append((A[i] if i % 2 == 0 else B[i], i))
        else:
            odds.append((A[i] if i % 2 == 1 else B[i], i))
    evens.sort()
    odds.sort()
    p = -1
    cnt = 0
    ok = True
    for i in range(N):
        c, mi = [evens, odds][i % 2][i // 2]
        if c < p:
            ok = False
            break
        p = c
        cnt += abs(mi - i)
    if ok:
        ans = min(ans, cnt // 2)
        # print(evens_i, ans, cnt, ok, evens, odds)
if ans == INF:
    print(-1)
else:
    print(int(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
for i in range(1000):
    if A == sorted(A):
        print(ans)
        quit()
    for i in range(N-1):
        a = A[i]
        ai = A[i+1]
        b = B[i]
        bi = B[i+1]
        if b > bi:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
        elif a > ai:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
red = list(map(int,input().split()))
blue = list(map(int,input().split()))
ans = 10 ** 5
for i in range(2 ** n):
    s = format(i,"b").zfill(n)
    print(s)
    num = [[red[j],j] if s[j] == "0" else [blue[j],j+1] for j in range(n)]
    num.sort()
    key = 1
    for h in range(n):
        if (num[h][1]-h) % 2 != 0:
            key = 0
    if key:
        ans = min(ans,max(s.count("1")-1,0))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

ret = float('inf')
for ce in combinations(range(N), (N + 1) // 2) :
  e, o = [], []
  for i in range(N) :
    if i in ce :
      if i % 2 == 0 :
        e.append([A[i], i])
      else :
        e.append([B[i], i])
    else :
      if i % 2 == 0 :
        o.append([B[i], i])
      else :
        o.append([A[i], i])
  
  e.sort()
  o.sort()
  s = []
  for i in range(N // 2) :
    s.append(e[i])
    s.append(o[i])
  if N % 2 != 0 :
    s.append(e[N // 2])
  
  for i in range(1, N) :
    if s[i] < s[i-1] :
      break
    
  else :
    tmp = 0
    for i in range(N) :
      tmp += s[i][1] - i
      for j in range(i + 1, N) :
        if s[j][1] < s[i][1] :
          s[j][1] += 1
    ret = min(ret, tmp)
    
if ret == float('inf') :
  print(-1)
else :
  print(ret)

Submission status: Wrong Answer

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