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())
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()
    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:
            ans = min(ans,nu//2)
if ans == 10 ** 5:
    print(-1)
else:
    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())
An = list(map(int,input().split(' ')))
Bn = list(map(int,input().split(' ')))
cnt = 0


def detect_min_value(start_an_idx,thred_value):
    belong = ''
    idx = 0
    min_number = 10**9
    while start_an_idx < N:
        if thred_value <= An[start_an_idx] < min_number:
            min_number = An[start_an_idx]
            belong = 'a'
            idx = start_an_idx
        if start_an_idx == N-1:
            break
        if thred_value <= Bn[start_an_idx+1] < min_number:
            min_number = Bn[start_an_idx+1]
            belong = 'b'
            idx = start_an_idx + 1
        start_an_idx += 2
    return belong,idx,min_number

def change_value(an_idx,replace_an_idx,cnt):
    for r_i in reversed(range(an_idx+1,replace_an_idx+1)):
           tmp = An[r_i]
           An[r_i] = Bn[r_i-1]
           Bn[r_i-1] = tmp

           tmp = An[r_i-1]
           An[r_i-1] = Bn[r_i]
           Bn[r_i] = tmp
    cnt += (replace_an_idx-an_idx)
    return cnt

for i in range(N):
    if i != 0:
        belong,replace_idx,min_number = detect_min_value(i,An[i-1])
    else:
        belong,replace_idx,min_number = detect_min_value(i,0)
    cnt = change_value(i,replace_idx,cnt)

min_value = (10**9 +7)*(-1)
for a in An:
    if min_value <= a:
        min_value = a
        continue
    else:
        print(-1)
        exit(0)
print(cnt)

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]*2 for _ in range(n+1)]

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

    if idx == n - 1:
        if arr == sorted(arr):
            # dp[idx] = cnt
            return cnt
        else:
            # dp[idx] = 10**10
            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][0] = cnt2
        dp[idx][1] = cnt1
        return cnt1
    else:
        dp[idx][0] = cnt2
        dp[idx][1] = cnt1
        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:
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 10**9+7
        else:
            if last <= b_list[i]:
                count = count + 1
                last = b_list[i]
                left_num = [left_num[1], left_num[0]]
            else:
                return 10**9+7
    if last <= left_num[0]:
        return count
    else:
        return 10**9+7

for checker in range(2**(n-1)):
    check_bin = '{0:018b}'.format(checker)
    min_count = min(min_count, check(check_bin))

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

Submission status: Wrong Answer

Solution code:
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:
def main():
    import sys
    from itertools import combinations
    input = sys.stdin.readline

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

        def sum(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

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

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

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

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

        bit = Bit(5100)
        ans_new = 0
        for i in range(N-1, -1, -1):
            ans_new += bit.sum(tmp[i]-1)
            bit.add(tmp[i], 1)
        #print(v, tmp, ans_new, odd, even)
        ans = min(ans, ans_new)

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


if __name__ == '__main__':
    main()

Submission status: 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]*2 for _ in range(n+1)]

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

    if idx == n - 1:
        if arr == sorted(arr):
            # dp[idx] = cnt
            return cnt
        else:
            # dp[idx] = 10**10
            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][1] = cnt1
        return cnt1
    else:
        dp[idx][0] = 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 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:
#!/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:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[(x,i) for i,x in enumerate(map(int,input().split()))]
    B=[(x,i) for i,x in enumerate(map(int,input().split()))]
    l_odd,l_even=[],[]
    for i in range(N):
        if i%2:
            l_even.append(A[i])
            l_odd.append(B[i])
        else:
            l_even.append(B[i])
            l_odd.append(A[i])
    stack=[]
    stack.append((0,0,[],[True]*N))
    kouho=[]
    while stack:
        n,index,l,f=stack.pop()
        if index==N:
            kouho.append(l)
            continue
        
        if index%2:
            C=l_even
        else:
            C=l_odd
        for a in C:
            if a[0]>=n and f[a[1]]:
                f2=[False]*N
                for i in range(N):
                    f2[i]=f[i]
                f2[a[1]]=False
                l2=l+[a[1]]
                stack.append((a[0],index+1,l2,f2))
    ans=INF
    if kouho:
        print(ans)
    else:
        print(-1)
    
            
    
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]

odd_bit = 0b0101010101010101010101
eve_bit = 0b1010101010101010101010
full_bit = 2**n - 1

odd_num = (n + 1) // 2
ans = 10**9 

for i in range(2**n):
    invi = full_bit ^ i
    odd = bin(i & odd_bit).count("1") + bin(invi & eve_bit).count("1")
    if odd != odd_num:
        continue
    odd_card = []
    eve_card = []
    for j in range(n):
        if i & 1 << j:
            if j % 2 == 0:
                odd_card.append((a[j], j))
            else:
                eve_card.append((a[j], j))
        else:
            if j % 2 == 1:
                odd_card.append((b[j], j))
            else:
                eve_card.append((b[j], j))
    odd_card.sort()
    eve_card.sort()
    odd_itr = 0
    eve_itr = 0
    curr = 0
    val = 0
    ok = True
    perm = []
    for i in range(n):
        if i % 2 == 0:
            num, index = odd_card[odd_itr]
            perm.append(index)
            odd_itr += 1
        else:
            num, index = eve_card[eve_itr]
            perm.append(index)
            eve_itr += 1
        if num < curr:
            ok = False
            break
        curr = num
    if ok:
        visited = [0] * n
        val = 0
        for i in range(n):
            if visited[i]:
                continue
            node = i
            length = 0
            while not visited[node]:
                length += 1
                visited[node] = 1
                node = perm[node]
            val += length - 1
        ans = min(ans, val)

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

Submission status: Wrong Answer

Solution code:
import copy
def get_swap_num(bin_num):
    tmpA = copy.copy(A)
    tmpB = copy.copy(B)
    swap_num = 0
    for idx, flag in enumerate(bin_num):
        if flag == '1':
            a1 = tmpA[idx]
            a2 = tmpA[idx+1]
            tmpA[idx] = tmpB[idx+1]
            tmpA[idx+1] = tmpB[idx]
            tmpB[idx+1] = a1
            tmpB[idx] = a2

            swap_num += 1

    for i in range(N-1):
        if tmpA[i] > tmpA[i+1]:
            return -1
    return swap_num


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = N + 1
for i in range(2**(N-1)):
    res = get_swap_num(bin(i)[2:].zfill(N-1))
    if res != -1:
        ans = min(ans, res)
if ans == N + 1:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
print(-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])
        Q.append((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 (a > ai) or (ai - a >= 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())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**n:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
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
    BIT=[0]*nn
    BIT.insert(0,0)
    for i1 in range(n):
      ct+=i1-bitsum(BIT,C[i1][1]+1)
      bitadd(BIT,C[i1][1]+1,1)


    
    ans=min(ans,ct)
print(-1 if ans==float("inf") else ans)

Submission status: Wrong Answer

Solution code:
import math
import itertools
import copy
 
N = int(input())
temp = input().split()
A = [int(i) for i in temp]
temp = input().split()
B = [int(i) for i in temp]
 
que = [[0,A,B]]
did_ques = [[A,B]]
while len(que) > 0:
    temp = que.pop(0)
    doingM = temp[0]
    doingA = temp[1]
    doingB = temp[2]
    #逆転があるか確認
    for i in range(N-1):
        if doingA[i] > doingA[i+1]:
            break
    else:
        #逆転が無かった時
        print(doingM)
        break
    #逆転があった時
    #二個入れ替えてAc,Bcを作り、被りがなければ登録
    for i in range(N-1):
        Ac,Bc = copy.copy(doingA),copy.copy(doingB)
        Ac[i],Ac[i+1],Bc[i],Bc[i+1] = Bc[i+1],Bc[i],Ac[i+1],Ac[i]
        #did_quesにかぶってるか確認
        for did_que in did_ques:
            if Ac == did_que[0] and Bc == did_que[1]:
                break
        else:
            #かぶりが無かった時
            que.append([doingM+1, Ac, Bc])
            did_ques.append([Ac, Bc])
if len(que) == 0:
    print(-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

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 = sorted(range(N), key=lambda x: X[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:
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]);card[1].sort(key=lambda x:num[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:
        ans = min(ans,sum(abs(hoge[i]-i)for i in range(N))//2)
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import sys
sys.setrecursionlimit(1 << 20)


def check(array):
    return array == sorted(array)


N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
n = set(range(N - 1))


def dfs(c, i, a, b):
    if c > 10:
        return float("inf")
    if c > 0 and a == A:
        return float("inf")
    if check(a):
        return c
    a[i], a[i+1], b[i], b[i+1] = b[i+1], b[i], a[i+1], a[i]
    ret = float("inf")
    for j in n.difference({i}):
        ret = min(ret, dfs(c+1, j, a, b))
    b[i + 1], b[i], a[i + 1], a[i] = a[i], a[i + 1], b[i], b[i + 1]
    return ret


ans = dfs(0, 0, copy.copy(A), copy.copy(B))
if ans == float("inf"):
    ans = -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:
        ans=-1
        break
ans_1=0
for i in range(2**n):
    for j in range(0,n-1,-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+=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+=1
        else:
            break
        continue
    else:
        ans_1=-1
        break
if ans==ans_1==-1:
    print(-1)
else:
    if ans==-1:
        print(ans_1)
    elif ans_1==-1:
        print(ans)
    else:
        print(min(ans,ans_1))

Submission status: Wrong Answer

Solution code:
def solve():
    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:
                Num[j] = A[j]
            else:
                Num[j] = B[j]
                back += 1
            if Num[j] not in original: original[Num[j]] = {j}
            else: original[Num[j]] |= {j}
            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 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)

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()))
res = float("inf")
for i in range(pow(2, N)):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  y = sorted(x)
  z = -1
  #print(y, i)
  for j in range(N):
    t = abs(j - y[j][1])
    #print(i & (1 << y[j][1]) > 0, t)
    if i & (1 << j) > 0:
      if t % 2:
        z = max(z, t)
      else:
        z = -1
        break
    else:
      if t % 2 == 0:
        z = max(z, t)
      else:
        z = -1
        break
  #print(y, z, i)
  if z >= 0:
    res = min(res, z)
if res != float("inf"): print(res)
else: print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 20)


def check(array):
    return array == sorted(array)


N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
n = set(range(N - 1))


def dfs(c, i, a, b):
    if c > 10:
        return float("inf")
    if c > 0 and a == A:
        return float("inf")
    if check(a):
        return c
    a[i], a[i+1], b[i], b[i+1] = b[i+1], b[i], a[i+1], a[i]
    ret = float("inf")
    for j in n.difference({i}):
        ret = min(ret, dfs(c+1, j, a, b))
    b[i + 1], b[i], a[i + 1], a[i] = a[i], a[i + 1], b[i], b[i + 1]
    return ret


ans = dfs(0, 0, A.copy(), B.copy())
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_lis = list(map(int, input().split()))
b_lis = list(map(int, input().split()))
used = []
res = []
def rec(a_lis, b_lis, l):
    
    found = True
    pre = -1
    for a in a_lis:
        if a < pre:
            found = False
            break
        pre = a
    if found:
        res.append(l)
        return
    used.append((a_lis, b_lis))
    for i in range(len(a_lis) - 1):
        na_lis = a_lis[:i] + [b_lis[i + 1]] + [b_lis[i]] + a_lis[i + 2:]
        nb_lis = b_lis[:i] + [a_lis[i + 1]] + [a_lis[i]] + b_lis[i + 2:]
        if (na_lis, nb_lis) not in used:
            rec(na_lis, nb_lis, l + 1)
if res:
    print(min(res))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
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]
        else:
            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)
else:
    print(ans)