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:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()
B = inpl()

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.node = [0]*(self.size + 1)
 
    def initialize(self, S):
        # S[0] = 0にしておく
        # 1-indexed
        if len(S) < self.size + 1:
            S += [S[-1]] * (self.size+1 - len(S))
        for i in range(1, self.size+1):
            self.node[i] = S[i] - S[i - (i&-i)]
 
    def sum(self, i):
        res = 0
        while i:
            res += self.node[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.node[i] += x
            i += (i & -(i))
 
    def bisect_left(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] < x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1
 
    def bisect(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] <= x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1

def bubble_sort(input_list, key):
    total_number = len(input_list)
    flag = True
    finished = 0

    while flag:
        flag = False
        for i in range(total_number-1-finished):
            if key[input_list[i]] > key[input_list[i+1]]:
                input_list[i], input_list[i+1] = input_list[i+1], input_list[i]
                flag = True
        finished += 1
    return input_list

ans = 10**9
g0 = itemgetter(0)
X = [0]*N
C = [0]*N
for i in range(2**N):
    I = i*1

    blue = 0
    for j in range(N):
        if I%2:
            X[j] = A[j]
            C[j] = 0
        else:
            X[j] = B[j]
            C[j] = 1
            blue += 1
        I //= 2
    if blue%2 == 1:
        continue
    tmp = 0
    I = list(range(N))
    I = bubble_sort(I, key=X)
    l = 0
    r = 0
    while l < N:
        for r in range(l, N):
            if X[I[l]] != X[I[r]]:
                break
        else:
            r = N
        p = 0
        for x in range(l, r-1):
            if (abs(x - I[x])+p)%2 != C[I[x]]:
                tmp += 1
                p = 1
            else:
                p = 0
        x = r-1
        if (abs(x - I[x]) + p)%2 != C[I[x]]:
            tmp = -1
            break
        l = r
    if (tmp != -1):
        bit = BIT(60)
        for j in range(N):
            bit.add(X[j], 1)
            tmp += j + 1 - bit.sum(X[j])
        ans = min(tmp, ans)
if (ans == 10**9):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [int(b) for b in input().split()]
    
    minmove = 1000000000
    for i in range(2 ** N):
        b = i
        back = 0
        Num = [None] * N
        original = dict()
        for j in range(N):
            if b % 2 == 0:
                n = A[j]
            else:
                n = B[j]
                back += 1
            if n not in original: original[n] = {j}
            else: original[n] |= {j}
            Num[j] = n
            b >>= 1
        if back % 2 > 0: continue
        Num.sort() #実現したい数列
        
        appeared = set()
        move = 0
        for j, n in enumerate(Num): #このソートが実現できるか
            for o in sorted(original[n]):
                if abs(j - o) % 2 == 0 and A[o] == n:
                    original[n] -= {o}
                    for key in appeared:
                        if key > o: move += 1
                    appeared |= {o}
                    break
                elif abs(j - o) % 2 == 1 and B[o] == n:
                    original[n] -= {o}
                    for key in appeared:
                        if key > o: move += 1
                    appeared |= {o}
                    break
            else: #実現できない
                break
        else: #実現できるため、操作回数を求める
            minmove = min(minmove, move)

    if minmove == 1000000000: print(-1)
    else: print(minmove)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import product
n=int(input())
kumiawase=list(product((0,1), repeat=n-1))
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=50
flag=0
for i in range(2**(n-1)):
    cnt=0
    out_flag=0
    kumi=kumiawase[i]
    C=[0]*n
    A2=A[:]
    B2=B[:]
    for j in range(n-1):
        if kumi[j]==0:
            C[j]=A2[j]
        else:
            C[j]=B2[j+1]
            A2[j+1],B2[j]=B2[j],A2[j+1]
            B2[j+1],A2[j]=A2[j],B2[j+1]
            cnt+=1
    C[n-1]=A2[n-1]
    for i in range(n-1):
        if C[i+1]-C[i]<0:
            out_flag=1
    if out_flag==0:
        ans=min(ans,cnt)
        flag=1
if flag==0:
    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()
    nu = 0
    for h in range(n):
        nu += abs(num[h][-1]-h)
        if ((num[h][1]) % 101-h) % 2 != 0:
            break
        if h == n-1:
            ans = min(ans,nu//2)
if ans == 10 ** 5:
    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 main():
  Ans=N**2+1
  for bits in range(1<<N):
    C=[A[i] if not (bits>>i)&1 else B[i] for i in range(N)]
    #print(C)
    #org=[A[i] if (bits>>i)&1 else B[i] for i in range(N)]
    cnt=[0 if not((bits>>i)&1) else 1 for i in range(N)]
    ans=0
    for i in range(N-1):
      for j in range(N-1,i,-1):
        if C[j]<C[j-1]:
          temp=C[j]
          C[j]=C[j-1]
          C[j-1]=temp
          temp=cnt[j]+1
          cnt[j]=cnt[j-1]+1
          cnt[j-1]=temp
          ans+=1
    #print(C,cnt)
    i=0
    flag=True
    while i<N:
      if cnt[i]%2:
        if i==N-1:
          flag=False
          break
        else:
          if A[i+1]!=A[i]:
            flag=False
            break
          else:
            i+=1
            ans+=1
      i+=1
    if flag:
      Ans=min(ans,Ans)
  if Ans==N**2+1:
    print(-1)
  else:
    print(Ans)
  return
          
main()

Submission status: Wrong Answer

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 count_inversion(sequence):
    return sum(sum(m < n for m in sequence[i+1:]) for i, n in enumerate(sequence))

for i in range(2**N):
    tmp = [0]*N
    count = 0
    for j in range(N):
        if (i >> j) % 2 == 1:
            tmp[j] = (A[j], j)
            count += 1
        else:
            tmp[j] = (B[j], j)

    tmp.sort()
    tmp_ans = 0
    flag = True
    tmp2 = [0]*N
    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
    if flag:
        tmp.sort(key=lambda x: x[1])
        tmp2 = [tmp[i][0] for i in range(N)]
        tmp_ans = count_inversion(tmp2)
        ans = min(tmp_ans, ans)

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

Submission status: Wrong Answer

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] = cost
        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: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 10**9+7
for i in range(2**N):
    card = [[],[]]
    num = []
    x = i
    for j in range(N):
        if i&1:
            num.append(B[j])
            card[(j+1)%2].append(j)
        else:
            num.append(A[j])
            card[(j)%2].append(j)
        i >>= 1
    if len(card[1]) != N//2:
        continue
    card[0].sort(key=lambda x:[num[x],x]);card[1].sort(key=lambda x:[num[x],x])
    hoge = []
    for i in range(N):
        hoge.append(card[i%2][i//2])
    flag = True
    for i in range(N-1):
        if num[hoge[i]] > num[hoge[i+1]]:
            flag = False
    if flag:
        huga = sum(abs(hoge[i]-i)for i in range(N))
        if huga % 2:
            print(1/0)
        else:
            huga //= 2
        if huga < ans:
            ans = huga
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a


# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get lower bound of index where w can be inserted
 
class Bit:
    def __init__(self,n):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        
    def __str__(self):
        return str(self.arr)
        
    def add(self,i,x):
        k=0
        while i<=self.size:
            k+=1
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
class Bit0(Bit):
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

show_flg=False
#show_flg=True

ans=inf

n=I()
a=LI()
b=LI()
m=1<<n


def Bsort(a):
    n=len(a)
    an=0
    N=52
    bt=Bit0(N)

    #x=n-1
    for i in range(n):
        c=bt.sum(N)-bt.sum(a[i])
        an+=c
        bt.add(a[i],1)
    return an

for i in range(m):
    c=[]
    parity=0
    f=[]
    
    if sum([1&(i>>j) for j in range(n)])%2==1:continue
        
    for j in range(n):
        if (i>>j)&1:
            c+=[b[j]]
            f+=[1]
        else:
            c+=[a[j]]
            f+=[0]
    
    y=[[] for _ in range(2)]
    ys=[[] for _ in range(2)]
    
    for j in range(n):
        y[(f[j]+j)%2].append(c[j])
        ys[(0*f[j]+j)%2].append(sorted(c)[j])
    if (set(y[0]),set(y[1]))==(set(ys[0]),set(ys[1])):
        ans=min(ans,Bsort(c))
    
    

if ans==inf:
    ans=-1
show('ans')
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
AA=[]
BB=[]
for i in range(n):
    if i%2==0:
        AA.append([A[i],i])
        BB.append([B[i],i])
    else:
        AA.append([B[i],i])
        BB.append([A[i],i])
l=[i for i in range(n)]
ans=-1
for v in itertools.combinations(l,(n+1)//2):
    AAA=[]
    BBB=[]
    c=0
    for i in range(n):
        if c!=(n+1)//2 and i==v[c]:
            AAA.append(AA[i])
            c+=1
        else:
            BBB.append(BB[i])
    AAA.sort()
    BBB.sort()
    flag=True
    for i in range(n-1):
        if i%2==0:
             if AAA[i//2][0]>BBB[i//2][0]:
                 flag=False
        else:
            if BBB[i//2][0]>AAA[(i+1)//2][0]:
                 flag=False
    if flag:
        ans_=0
        for i in range(len(AAA)):
            ans_+=abs(AAA[i][1]-i*2)
        for i in range(len(BBB)):
            ans_+=abs(BBB[i][1]-i*2-1)
        ans_//=2
        if ans==-1:
            ans=ans_
        else:
            ans=min(ans_,ans)
print(ans)

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
            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:
                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 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__':
    examD()


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

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(1<<n):
    rev = [False for _ in range(n)]
    t = 0
    for bit in range(n):
        if i>>bit&1:
            rev[bit] = True
            t += 1
    if t%2 == 1:continue
    data_odd = []
    data_even = []
    for j in range(n):
        if rev[j]:
            if j%2 == 0:
                data_odd.append([b[j],j])
            else:
                data_even.append([b[j],j])
        else:
            if j%2 == 0:
                data_even.append([a[j],j])
            else:
                data_odd.append([a[j],j])

    if len(data_odd) != n//2:continue
    data_odd.sort()
    data_even.sort()
    q = True
    data  = []
    for j in range(n):
        if j%2 == 0:
            if  j>= 1 and data_even[j//2] < data_odd[j//2-1]:
                q = False
                break
            else:
                data.append(data_even[j//2][1])
        else:
            if j>=1 and data_odd[j//2] < data_even[(j-1)//2]:
                q = False
                break
            else:
                data.append(data_odd[j//2][1])

    if not q:continue
    res = 0
    for j in range(n):
        for k in range(j+1,n):
            if data[j] > data[k]:
                res += 1
                p = data[k]
                data[k] = data[j]
                data[j] = p
    ans = min(res,ans)
print(ans if ans < 10**9 else -1)

Submission status: Wrong Answer

Solution code:
#  --*-coding:utf-8-*--

MAX = 10**9
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

flags = 0
cache = {}

def f(pos, lastVal):
    global flags

    if pos == N:
        return 0

    key = (flags, lastVal)
    if key in cache:
        return cache[key]

    minCnt = MAX

    for i in range(N):
        bit = 1<<i;

        if flags&bit == 0:
            val = A[i] if (pos-i)%2 == 0 else B[i]
            if val >= lastVal:
                flags ^= bit
                minCnt = min(minCnt, f(pos+1, val) + abs(pos-i))
                flags ^= bit
                         
    cache[key] = minCnt
    return minCnt

ans = f(0, 0)
print(ans//2 if ans < MAX 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(2**18):
    for j in range(n-1):
        if a!=sorted(a):
            if a[j+1]>b[j] and a[j]>b[j+1]:
                a[j+1],b[j]=b[j],a[j+1]
                a[j],b[j+1]=b[j+1],a[j]
                ans+=1
            elif a[j]<a[j+1] and b[j]>b[j+1]:
                a[j+1],b[j]=b[j],a[j+1]
                a[j],b[j+1]=b[j+1],a[j]
                ans+=1
            elif a[j]>a[j+1]:
                a[j+1],b[j]=b[j],a[j+1]
                a[j],b[j+1]=b[j+1],a[j]
                ans+=1
        else:
            break
        continue
    else:
        ans=-1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a


# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get lower bound of index where w can be inserted
 
class Bit:
    def __init__(self,n):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        
    def __str__(self):
        return str(self.arr)
        
    def add(self,i,x):
        k=0
        while i<=self.size:
            k+=1
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
class Bit0(Bit):
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

show_flg=False
#show_flg=True

ans=inf

n=I()
a=LI()
b=LI()
m=1<<n


def Bsort(a):
    n=len(a)
    an=0
    N=52
    bt=Bit0(N)

    #x=n-1
    for i in range(n):
        c=bt.sum(N)-bt.sum(a[i]+1)
        an+=c
        bt.add(a[i],1)
    return an

for i in range(m):
    c=[]
    parity=0
    f=[]
    
    if sum([1&(i>>j) for j in range(n)])%2==1:continue
        
    for j in range(n):
        if (i>>j)&1:
            c+=[b[j]]
            f+=[1]
        else:
            c+=[a[j]]
            f+=[0]
    
    y=[[] for _ in range(2)]
    ys=[[] for _ in range(2)]
    
    for j in range(n):
        y[(f[j]+j)%2].append(c[j])
        ys[(0*f[j]+j)%2].append(sorted(c)[j])
    if (set(y[0]),set(y[1]))==(set(ys[0]),set(ys[1])):
        ans=min(ans,Bsort(c))
    
    

if ans==inf:
    ans=-1
show('ans')
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1


def babble_sort(arr):
    """ バブルソート """
    length = len(arr)
    count=0
    data=[i for i in range(length)]
    swap=[0]*length

    for i in range(length):
        # 3. 走査範囲を前からひとつ狭める
        for j in reversed(range(i+1, length)):
            # 1. 後ろから順に隣り合う要素を比較する。
            if arr[j-1] > arr[j]:
                # 2. 左が右の要素に比べ大きい場合交換する。
                arr[j-1], arr[j] = arr[j], arr[j-1]
                data[j-1], data[j] = data[j], data[j-1]
                swap[data[j]]+=1
                swap[data[j-1]]+=1
                count+=1
    return count,swap


n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
for bit in range(2**n):
    if sum(map(int,str(bit)))%2!=0:
        continue
    tar=[0]*n
    data=[0]*n
    for i in range(n):
        if (bit>>i & 1):
            tar[i]=B[i]; data[i]=1
        else:
            tar[i]=A[i]
    tmp,swap=babble_sort(tar[:])
    S=[0]*51
    for i in range(n):
        if swap[i]%2!=data[i]:
        #     if S[tar[i]]:
        #         S[tar[i]]=0
        #     else:
        #         S[tar[i]]=1
        # elif S[tar[i]]:
            break
    else:
        mans=min(mans,tmp)
    continue
print(-1 if mans==inf else mans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 10**9+7
for i in range(2**N):
    card = [[],[]]
    num = []
    x = i
    for j in range(N):
        if i&1:
            num.append(B[j])
            card[(j+1)%2].append(j)
        else:
            num.append(A[j])
            card[(j)%2].append(j)
        i >>= 1
    if len(card[1]) != N//2:
        continue
    card[0].sort(key=lambda x:[num[x],x]);card[1].sort(key=lambda x:[num[x],x])
    hoge = []
    for i in range(N):
        hoge.append(card[i%2][i//2])
    flag = True
    for i in range(N-1):
        if num[hoge[i]] > num[hoge[i+1]]:
            flag = False
    if flag:
        huga = sum(abs(hoge[i]-i)for i in range(N))//2
        if huga < ans:
            ans = huga
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()
    nu = 0
    for h in range(n):
        nu += abs(num[h][-1]-h)
        if ((num[h][1])%101-h) % 2 != 0:
            break
        if h == n-1:
            ans = min(ans,nu//2)
if ans == 10 ** 5:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
from bisect import bisect_left

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

N = ir()
A = [(x, i) for i, x in enumerate(lr())]
B = [(x, i) for i, x in enumerate(lr())]
odd = A[::2] + B[1::2] #奇数番目のカードでしか表にならない
even = A[1::2] + B[::2]
odd.sort()
even.sort()
# 最初のカードを全通り試す

def F(i, right, OE, OE2, x, used, count):
    global answer
    #左からi番目にOE(oddかeven)のsortした後のx番目のカードを入れる
    #今まで使ったカードはused、操作回数はcount(最後に２で割る)
    used.add(OE[x][1])
    count += abs(i-OE[x][1])
    right = OE[x][0]
    if i == N-1:
        count //= 2
        if count < answer:
            answer = count
        return
   
    j = bisect_left([y for y, z in OE2], right)
    
    for k in range(j, min(N, (i+2)*2)):
        if OE2[k][1] in used:
            continue
        F(i+1, right, OE2, OE, k, used, count)

INF = 10 ** 19
answer = INF
for i in range(N):
    F(0, 0, odd, even, i, set(), odd[i][1])

print(answer if answer < 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(2**n):
    for j in range(n-1):
        if a!=sorted(a):
            if a[j+1]>b[j] and a[j]>b[j+1]:
                a[j+1],b[j]=b[j],a[j+1]
                a[j],b[j+1]=b[j+1],a[j]
                ans+=1
            elif a[j]<a[j+1] and b[j]>b[j+1]:
                a[j+1],b[j]=b[j],a[j+1]
                a[j],b[j+1]=b[j+1],a[j]
                ans+=1
            elif a[j]>a[j+1]:
                a[j+1],b[j]=b[j],a[j+1]
                a[j],b[j+1]=b[j+1],a[j]
                ans+=1
        else:
            break
        continue
    else:
        ans=-1
        break
print(ans)