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:
import copy
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ab = []

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

# print(ab)
dp = [None]*n

def solve(idx, arr, cnt):
    if dp[idx] is not None:
        return dp[idx]

    if idx == n - 1:
        if arr == sorted(arr):
            return cnt
        else:
            return 10**10
    # Reverse
    new = copy.deepcopy(arr)
    new[idx][0], new[idx][1], new[idx+1][0], new[idx+1][1] = new[idx+1][1], new[idx+1][0], new[idx][1], new[idx][0]
    cnt1 = solve(idx+1, new, cnt+1)

    # Not reverse
    cnt2 = solve(idx+1, arr, cnt)

    if cnt1 < cnt2:
        dp[idx] = cnt1
        # return cnt1
    else:
        dp[idx] = cnt2
        # return cnt2
    return dp[idx]

ans = solve(0, ab, 0)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:


import time
stime=time.time()

N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
ans=0
f=True
while True:
    t=1
    for i in range(N-1):
        if A[i]>A[i+1]:
            t=0
    if t==1:
        break
    for i in range(N-1):
        if A[i]>A[i+1]:
            if B[i]>B[i+1]:
                x_A=[A[i], A[i+1]]
                A[i],A[i+1]=(B[i+1], B[i])
                B[i],B[i+1]=(x_A[1], x_A[0])
                ans+=1
            elif i>=1:
                if B[i-1]>B[i]:
                    x_A=[A[i-1], A[i]]
                    A[i-1],A[i]=(B[i], B[i-1])
                    B[i-1],B[i]=(x_A[1], x_A[0])
                    ans+=1
    if time.time()-stime>1.5:
        f=False
        break
if f:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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()
        xx1.sort(key=lambda x: x[1])
        if ng():continue
        #print(xx0)
        #print(xx1)
        kk=[]
        for [_,_,i0],[_,_,i1] in zip(xx0,xx1):
            kk+=[i0,i1]
        if n%2:kk+=[xx0[-1][2]]
        #print(kk)
        ans=change(ans)
    if ans==1000:print(-1)
    else:print(ans)

main()

Submission status: Wrong Answer

Solution code:
from itertools import product
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
for x in product((0,1),repeat=N):
    C = [0 for _ in range(N)]
    for i in range(N):
        if x[i]==0:
            C[i] = (A[i],i)
        else:
            C[i] = (B[i],i)
    C = sorted(C,key=lambda x:x[0])
    flag = 1
    for i in range(N):
        j = C[i][1]
        if x[j]==0:
            if i%2!=j%2:
                flag = 0
                break
        else:
            if i%2!=1-j%2:
                flag = 0
                break
    if flag==1:
        break
if flag==0:
    cnt = -1
else:
    C = sorted(C,key=lambda x:x[1])
    cnt = 0
    for i in range(1,N):
        a = C[i][0]
        for j in range(i):
            if C[j][0]>a:
                cnt += 1
print(cnt)

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 = []
        for j in range(N):
            if i&(1<<j)==(1<<j):
                cur +=1
                nowA.append(B[j])
            else:
                nowA.append(A[j])
        if cur%2==1:
            continue
        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)):
                    if ((abs(v-j)%2)==1 and i&(1<<v)==(1<<v)) or ((abs(v-j)%2)==0 and i&(1<<v)==0):
                        candi = min(candi,abs(v-j))
                if ((abs(v-j)%2)==0 and i&(1<<j)==0):
                    if ((abs(v - j) % 2) == 1 and i & (1 << v) == (1 << v))or((abs(v-j)%2)==0 and i&(1<<v)==0):
                        candi = min(candi,abs(v-j))
            if candi==inf:
#                print(dist, i & (1 << j),i,j)
                now = inf
                break
            else:
                now +=candi
        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:
from itertools import permutations
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
minc = 19
num = [i for i in range(N-1)]
for i in range(N-1):
    for j in permutations(num,i):
        now = 0
        flag = True
        count = len(j)
        A2 =  A.copy()
        B2 =  B.copy()
        for k in j:
            A2[k],A2[k+1],B2[k],B2[k+1] = B2[k+1],B2[k],A2[k+1],A2[k]

        for j in A2:
            if now <= j:
                now = j
            else:
                flag = False
                break
        if flag:
            minc = min(minc,count)
if minc != 19:
    print(minc)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import copy
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
aa=copy.deepcopy(a)
bb=copy.deepcopy(b)
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
        else:
            break
        continue
    else:
        ans=-1
        break
if ans==-1:
    ans=0
    a=copy.deepcopy(aa)
    b=copy.deepcopy(bb)
    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] and a[j+1]>b[j]:
                    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:
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            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
n=int(input())
*a,=map(int,input().split())
*b,=map(int,input().split())
m=10**18
for i in range(2**n):
    t,u=[],[]
    x=y=0
    for j in range(n):
        f=1if 2**j&i>0else 0
        if f:
            if j%2:
                t+=b[j],
            else:
                u+=b[j],
        else:
            if j%2:
                u+=a[j],
            else:
                t+=a[j],
        if j%2:
            x+=f
        else:
            y+=f
    if x!=y:
        continue
    l=[]
    for p,q in zip(sorted(t),sorted(u)):
        l+=p,
        l+=q,
    if len(t)>len(u):
        l+=max(t),
    if l!=sorted(l):
        continue
    bit=BIT(64)
    v=0
    for j,p in enumerate(t):
        bit.add(p,1)
        v+=j+1-bit.sum(p)
    bit=BIT(64)
    w=0
    for j,p in enumerate(u):
        bit.add(p,1)
        w+=j+1-bit.sum(p)
    m=min(m,v+w+x)
if m==10**18:
    print(-1)
else:
    print(m)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
from collections import defaultdict
import time
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
d = defaultdict(int)
Q = [(0,X)]
while Q:
    if time.time()-start>1.7:break
    q = heappop(Q)
    A = [e[0] for e in q[1]]
    if A==sorted(A):
        ans=max(q[0],ans)
        break
    if d[str(q[1])]:continue
    d[str(q[1])]=1
    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 = 0
for i in range(10000):
    for i in range(N-1):
        if A == sorted(A):
            print(ans)
            quit()
        a = A[i]
        ai = A[i+1]
        b = B[i]
        bi = B[i+1]
        if b > bi:
            if b < ai:
                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())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]

ans = 1 << 100
for m in range(1<<N):
    if bin(m).count("1") & 1: continue
    C = [(A[i] if m >> i & 1 == 0 else B[i], i + (m >> i) & 1) for i in range(N)]
    CC = [(-1, 0), (-1, 0)] + sorted(C) + [(51, 0), (51, 0)]
    D = [{}, {}]
    for i in range(N):
        if CC[i+2][0] > CC[i][0]:
            D[i&1][CC[i+2][0]] = [i, i]
        if CC[i+2][0] < CC[i+4][0]:
            D[i&1][CC[i+2][0]][1] = i
    s = 0
    for i, (x, p) in enumerate(C):
        if x not in D[p]:
            break
        l, r = D[p][x]
        s += abs(i - l)
        if l == r:
            del D[p][x]
        else:
            l += 2
    else:
        ans = min(ans, s)
print(ans // 2 if ans < 1 << 100 else -1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product

def solve(N: int, A: "List[int]", B: "List[int]"):

    AB = list(zip(A,B))
    answer = 10**18
    
    #0が表,1が裏返す
    for bit in product([0,1],repeat=N):
        num_list = []
        #(数字,表か裏か,元々のindex)
        for i in range(N):
            num_list.append((AB[i][bit[i]],bit[i],i))
        num_list.sort(key=lambda x: x[0])

        move_dist = 0
        for i in range(N):
            _, flag, index = num_list[i]

            if abs(i-index)%2 != flag:
                break

            move_dist += abs(i-index)
        else: ## 可能な移動である
            if move_dist%2 == 0:
                answer = min(answer,move_dist//2)
    if answer == 10**18:
        print(-1)
    else:
        print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import copy

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
Ai=[[] for _ in range(N)]
Bi=[[] for _ in range(N)]

for i in range(N):
    Ai[i]=[A[i],i]
    Bi[i]=[B[i],i]

ans=10**9
for i in range(N//2+1):#青の枚数の取り方
    blue=i*2
    for ite in itertools.combinations(range(N), blue):#青の取り方
        cardset=copy.deepcopy(Ai)
        temp=0
        flag=1
        for k in range(len(ite)):#cadset作成
            cardset[ite[k]]=Bi[ite[k]]
        cardset.sort()
        for ii in range(N):#1枚ずつ移動判定
            d=abs(ii-cardset[ii][1])#移動距離
            if ii in ite:
                rb=1#青
            else:
                rb=0
            if d%2!=rb:
                flag=0
                break
            temp+=d
        if flag==1:
            ans=min(ans,temp//2)
          

if ans==10**9:
    ans=-1

print(ans)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#Binary Indexed Tree (1-indexなので注意！！！！！！！！)
class BinaryIndexedTree():
    def __init__(self, size):
        self.__node=[0]*(size+1)
        self.size = size

    #node[index]にvalueを足して、BITを更新
    def add(self, index, value):
        while index <= self.size:
            self.__node[index] += value
            index += index&-index    
    
    #indexまでの和を返す
    def sum(self, index):
        ret = 0 #零元・単位元
        while index > 0:
            ret += self.__node[index]
            index -= index&-index    
        return ret

    def update_max(self, index, value):
        while index <= self.size:
            self.__node[index] = max(self.__node[index], value)
            index += index & -index


    #indexまでの最大値を返す
    def query_max(self, index):
        ret = 0
        while index > 0:
            ret = max(ret, self.__node[index])
            index -= index & -index
        return ret
        
        

    #0-indexでの添字を受け取って、1-indexでの添字での値を返す
    def get_node(self, index):
        return self.__node[index]
def main():
    N=I()
    A=LI()
    B=LI()
    max_bit = 1<<N

    def Inversion_number(A):
        N=len(A)
        B=sorted(set(A))
        BIT = BinaryIndexedTree(N)
        res = 0
        for i in range(N):
            idx = bisect_left(B,A[i])
            res += i - BIT.sum(idx+1)
            BIT.add(idx+1,1)
        return res

        
    def check(mask):
        C=[0]*N
        for i in range(N):
            if not (mask>>i&1):
                C[i] = (A[i],i)
            else:
                C[i] = (B[i],i)
        res = Inversion_number(C)
        C.sort()
        dic = defaultdict(int)
        for j,(c,i) in enumerate(C):
            dic[c,j&1] += 1
        # print(dic)
        
        for i in range(N):
            if not (mask>>i&1):
                num,is_odd_idx = A[i],i&1
                if dic[num,is_odd_idx]:
                    dic[num,is_odd_idx]-=1
                else:
                    return inf
            else:
                num,is_odd_idx = (B[i],i&1)
                if dic[num,is_odd_idx^1]:
                    dic[num,is_odd_idx^1]-=1
                else:
                    return inf
        # print(bin(mask)[2:],C)
        
        return res


    ans = inf
    for mask in range(max_bit):
        res = check(mask)
        if res < ans:
            ans = res
    if ans == inf:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

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
p = 0
for h in range(1000):
  for i in range(n-1):
      flag = True
      if a[i+1] < a[i]:
        if i != 0 :
          aflag = a[i]
          aflag2 = a[i-1]
          a[i] = b[i-1]
          a[i-1] = b[i]
          b[i-1] = aflag
          b[i] = aflag2
          ac += 1    
        else:
          aflag = a[i]
          aflag2 = a[i+1]
          a[i+1] = b[i]
          a[i] = b[i+1]
          b[i] = aflag2
          b[i+1] = aflag
          ac += 1         
  
          
          
for i in range(n-1):
  if a[i] > a[i+1]:
    print(-1)
    sys.exit()
print(ac)

Submission status: Wrong Answer

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N=int(input())

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

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


def flip(i):
	k=A[i]
	A[i]=B[i+1]
	B[i+1]=k
	l=B[i]
	B[i]=A[i+1]
	A[i+1]=B[i]
	
if A==sorted(A):
	print("0")
else:
	print("-1")

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))

min_count = 10**9+7

def check(bin_list):
    last = 0
    count = 0
    left_num = [a_list[0],b_list[0]]
    for i in range(1,n):
        if bin_list[-i] == '0':
            if last <= left_num[0]:
                last = left_num[0]
                left_num = [a_list[i], b_list[i]]
            else:
                return False
        else:
            if last <= b_list[i]:
                count = count + 1
                last = b_list[i]
                left_num = [left_num[1], left_num[0]]
            else:
                return False
    if last <= left_num[0]:
        return count
    else:
        return False

for checker in range(2**(n-1)):
    check_bin = '{0:017b}'.format(checker)
    ans = check(check_bin)
    if not(ans is False):
        min_count = min(min_count, ans)

print(min_count if min_count != 10**9+7 else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
from collections import defaultdict
import time
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
d = defaultdict(int)
Q = [(0,X)]
while Q:
    if time.time()-start>1.6:break
    q = heappop(Q)
    A = [e[0] for e in q[1]]
    if A==sorted(A):
        ans=max(q[0],ans)
        break
    if d[str(q[1])]:continue
    d[str(q[1])]=1
    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:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
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

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

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
b_ls = [int(i) for i in sys.stdin.readline().split()]
ls = list(zip(a_ls, b_ls))

count = 0

def merge(a, left, mid, right):
    global count
    l = a[left:mid] + [[float("inf")]*3]
    r = a[mid:right] + [[float("inf")]*3]
    i = j = 0
    for k in range(left, right):
        if l[i][2] <= r[j][2]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            count += len(l) - i - 1

def mergeSort(a, left, right):
    if left + 1 < right:
        mid = right + (left - right)//2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)


_min = 10**18
flg = False
for i in range(1 << n):
    cur = []
    count = 0
    one_count = 0
    for j, (k, l) in enumerate(zip(bin(i)[2:].zfill(n), ls)):
        one_count += int(k)
        cur.append((int(k), j % 2, l[int(k)]))
    if one_count % 2 != 0:
        continue
    mergeSort(cur, 0, len(cur))
    if all([j[0] == (j[1] != ind % 2) for ind, j in enumerate(cur)]):
        flg = True
        _min = min(_min, count)
if flg:
    print(_min)
else:
    print(-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(10000):
    for i in range(N-1):
        if A == sorted(A):
            print(ans)
            quit()
        a = A[i]
        ai = A[i+1]
        b = B[i]
        bi = B[i+1]
        if b > bi:
            if ai - a >= b - bi:
                A[i] = bi
                A[i+1] = b
                B[i] = ai
                B[i+1] = a
                ans += 1
        elif a > ai:
            if bi - b <= 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())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))

minimum = None

def find(lists, i, goal, count):
	global minimum
	if minimum != None and count >= minimum:
		return
#	print(i, lists[0])
#	print(i, lists[1])
#	print(i, goal)
#	print()
	g = goal[i]
	if i == N - 1:
		if lists[0][i] == g:
			minimum = count
	else:
		for j in range(i, N):
			if lists[(j - i) % 2][j] == g:
#				print(f"f: {i} to {j}")
				new_lists = [lists[0].copy(), lists[1].copy()]
				for k in range(i, j):
					new_lists[0][k], new_lists[1][k], new_lists[0][k + 1], new_lists[1][k + 1] = (new_lists[1][k + 1], new_lists[0][k + 1], new_lists[1][k], new_lists[0][k])
				find(new_lists, i + 1, goal, count + j - i)

checked = set()
values = [0] * N
for i in range(2 ** N):
	for j in range(N):
		if i % 2 == 1:
			values[j] = A_list[j]
		else:
			values[j] = B_list[j]
		i //= 2
	values.sort()
	goal = tuple(values)
	if goal not in checked:
		find([A_list, B_list], 0, goal, 0)
		checked.add(goal)

if minimum == None:
	print("-1")
else:
	print(minimum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
flag = False
ans = 0
count = 0
while True:
    if count == 10**5:
        ans = -1
        break
    for i in range(1,N):
        if A[i-1] > A[i]:
            break
        if i == N-1:
            flag = True
    if flag:
        break
    for i in range(1,N):
        if (B[i-1] > B[i] or A[i-1] > A[i]) and B[i-1] <= A[i]:
            tmpA = [A[i-1],A[i]]
            tmpB = [B[i-1],B[i]]
            A[i-1],A[i] = tmpB[1],tmpB[0]
            B[i-1],B[i] = tmpA[1],tmpA[0]
            ans += 1
    count += 1
print(ans)

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=n
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]
        elif kumi[j]==1:
            C[j]=B2[j+1]
            A2[j+1]=B2[j]
            B2[j+1]=A2[j]
            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)
elif flag==1:
    print(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(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] and a[j+1]>b[j]:
                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:
        #print(a)
        #print(b)
        ans=-1
        break
print(ans)

Submission status: Wrong Answer

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

dp=[(0,0,0)]*n
flag=0
buf=0
count=10**9
for i in range(2**n):
    flag=0
    for j in range(n):
        if bin(i)[2:].zfill(n)[j]=='0':
            dp[j]=(a[j]+j/n,j,0)
        else:
            dp[j]=(b[j]+j/n,j,1)
    dp.sort()
    for j in range(n):
        if ((dp[j][1]-j)%2)!=dp[j][2]:
            flag=1
            break
    if flag==1:
        continue
    else:
        buf=0
        for j in range(n):
            if j>dp[j][1]:
                buf+=j-dp[j][1]
        count=min(count,buf)
if count==10**9:
    print(-1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
import time
n = int(input())
red = list(map(int,input().split()))
blue = list(map(int,input().split()))
  # start = time.time()
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()
    nu = 0
    for h in range(n):
        nu += abs(num[h][-1]-h)
        if (num[h][1]-h) % 2 != 0:
            break
        if h == n-1:
  #            print(num)
            ans = min(ans,nu//2)
  #real_time = time.time()-start
  # print(real_time)
if ans == 10 ** 5:
    print(-1)
else:
    print(ans)