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: Time Limit Exceeded

Solution code:
from collections import defaultdict
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    if n.count('1')%2!=0:
        continue
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i])
        else:
            l.append([B[i],i+1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort(key=itemgetter(0,1))
    d = defaultdict(list)
    for i in range(N):
        v,j = l[i]
        if (i-j)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

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

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    if n.count('1')%2!=0:
        continue
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i])
        else:
            l.append([B[i],i+1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort()
    d = defaultdict(list)
    for i in range(N):
        v,j = l[i]
        if (i-j)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

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

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i])
        else:
            l.append([B[i],i+1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort()
    d = defaultdict(list)
    for i in range(N):
        v,j = l[i]
        if (i-j)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

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

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i,0])
        else:
            l.append([B[i],i,1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort()
    d = defaultdict(list)
    for i in range(N):
        v,j,k = l[i]
        if (i-j+k)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

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

ans = float('inf')
for n in range(2**N):
    n = bin(n)[2:]
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i,0])
        else:
            l.append([B[i],i,1])
    inversion = 0
    for i in range(N):
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    l.sort()
    d = defaultdict(list)
    for i in range(N):
        v,j,k = l[i]
        if (i-j+k)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

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

Submission status: Time Limit Exceeded

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

ans = float('inf')
for n in range(2**N):
    n = bin(n)[2:]
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i,0])
        else:
            l.append([B[i],i,1])
    inversion = 0
    for i in range(N):
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    l.sort()
    d = defaultdict(list)
    for i in range(N):
        v,j,k = l[i]
        if (i-j+k)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
odd = []
even = []

for i in range(n):
    if i % 2 == 0:
        even.append(a[i])
        odd.append(b[i])
    else:
        even.append(b[i])
        odd.append(a[i])
#odd, evenの二部グラフで、自身に辺を通さない
#a[i] <=  b[j]の時辺を通す 
graph = [[] for i in range(n*2)]
for i in range(n):
    for j in range(n, n*2):
        if i != j % n and even[i] <= odd[j%n]:
            graph[i].append(j)

for i in range(n,n*2):
    for j in range(n):
        if  j != i % n and odd[i % n] <= even[j]:
            graph[i].append(j)
#グラフで一筆書きをする。パスがnになったら終わり。その順番を実現するために考える
def clear_maze(start):
    que = deque()
    que.append([start, set([start]), [start]])
    while que:
        node, f, p = que.popleft()
        if len(p) == n:
            check(p)
        else:
            for i in graph[node]:
                if i % n not in f:
                    que.append([i, f|set([i%n]), p + [i]])

def check(path):
    #この順番に並ぶための最小
    array = [i % n for i in path]
    global ans
    ans = min(mergecount(array), ans)
def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1=0
        i2=0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt
inf = 18**2
ans = inf
for i in range(n):
    #iから始める迷路を解く
    clear_maze(i)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    if i % 2 == 0:
        even.append(a[i])
        odd.append(b[i])
    else:
        even.append(b[i])
        odd.append(a[i])
#odd, evenの二部グラフで、自身に辺を通さない
#a[i] <=  b[j]の時辺を通す 
graph = [[] for i in range(n*2)]
for i in range(n):
    for j in range(n, n*2):
        if i != j % n and even[i] <= odd[j%n]:
            graph[i].append(j)

for i in range(n,n*2):
    for j in range(n):
        if  j != i % n and odd[i % n] <= even[j]:
            graph[i].append(j)
#グラフで一筆書きをする。パスがnになったら終わり。その順番を実現するために考える
def clear_maze(start, finished, path):
    f = finished | set([start%n])
    path = path + [start]
    if len(path) == n:
        check(path)
    else:
        for i in graph[start]:
            if (i % n not in f):
                clear_maze(i, f, path)
def check(path):
    #この順番に並ぶための最小
    #print(path)
    array = [i % n for i in path]
    global ans
    ans = min(mergecount(array), ans)
def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1=0
        i2=0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt
inf = 18**2
ans = inf
for i in range(n):
    #iから始める迷路を解く
    clear_maze(i, set(), [])
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# from collections import defaultdict,deque
# import sys,heapq,bisect,math,itertools,string,queue,copy,time
# sys.setrecursionlimit(10**8)
#
#
import sys
import itertools
INF = float("INF")

N = int(input())
AA = list(map(int, sys.stdin.readline().split()))
BB = list(map(int, sys.stdin.readline().split()))

cards = set()
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.add((a, b, i))
    else:
        cards.add((b, a, i))

def solve(ii):
    tmp = 0
    for _ in range(N):
        next = []
        for k, i in enumerate(ii):
            if i == 0:
                tmp += k
            else:
                next.append(i-1)
        ii = next[:]
    return tmp

ans = INF
for Acards in itertools.combinations(cards, (N+1)//2):
    Bcards = cards - set(Acards)

    Ais = sorted([(card[0], card[2]) for card in Acards])
    Bis = sorted([(card[1], card[2]) for card in Bcards])

    bn = -1
    ii = []
    flag = False
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        if bn > n:
            flag = True
        bn = n
        ii.append(i)

    if flag: continue

    ans = min(ans,solve(ii))


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

Submission status: Time Limit Exceeded

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

v = [[0, 0] for _ in range(N)]
s = []
ans = 500

for i in range(1<<N):
    tmp = 0
    for j in range(N):
        if ((i>>j)&1): v[j] = [B[j], j]
        else:          v[j] = [A[j], j]
    for j in range(N):
        p = j
        while (p and v[p][0] < v[p-1][0]):
            v[p], v[p-1] = v[p-1], v[p]
            tmp += 1
            p -= 1
    for j in range(N):
        if (((i>>v[j][1])+v[j][1]-j)&1):
            s.append(v[j][0]*500+j)
    if (len(s)&1):
        tmp = 500
        s.pop()
    while s:
        p = s.pop()
        q = s.pop()
        if ((p-q)&1): tmp += p-q
        else:         tmp += 500
    ans = min(ans, tmp)

if ans < 500:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

for i in range(n):
    if i % 2 == 0:
        even.append(a[i])
        odd.append(b[i])
    else:
        even.append(b[i])
        odd.append(a[i])
#odd, evenの二部グラフで、自身に辺を通さない
#a[i] <=  b[j]の時辺を通す 
graph = [[] for i in range(n*2)]
for i in range(n):
    for j in range(n, n*2):
        if i != j % n and even[i] <= odd[j%n]:
            graph[i].append(j)

for i in range(n,n*2):
    for j in range(n):
        if  j != i % n and odd[i % n] <= even[j]:
            graph[i].append(j)
#グラフで一筆書きをする。パスがnになったら終わり。その順番を実現するために考える
def clear_maze(start, finished, path):
    f = finished | set([start%n])
    path = path + [start]
    if len(path) == n:
        check(path)
    else:
        for i in graph[start]:
            if (i % n not in f):
                clear_maze(i, f, path)
def check(path):
    #この順番に並ぶための最小
    #print(path)
    array = [i % n for i in path]
    cand = 0
    global ans
    for i in range(1,n,1):
        for j in range(i,n,1):
            if array[i-1] > array[j]:
                cand += 1
    ans = min(cand, ans)
inf = 18**2
ans = inf
for i in range(n):
    #iから始める迷路を解く
    clear_maze(i, set(), [])
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    if i % 2 == 0:
        even.append(a[i])
        odd.append(b[i])
    else:
        even.append(b[i])
        odd.append(a[i])
#odd, evenの二部グラフで、自身に辺を通さない
#a[i] <=  b[j]の時辺を通す 
graph = [[0 for __ in range(n*2)] for _ in range(n*2)]
for i in range(n):
    for j in range(n, n*2):
        if i != j % n and even[i] <= odd[j%n]:
            graph[i][j] = 1

for i in range(n,n*2):
    for j in range(n):
        if  j != i % n and odd[i % n] <= even[j]:
            graph[i][j] = 1
#グラフで一筆書きをする。パスがnになったら終わり。その順番を実現するために考える
def clear_maze(start, finished, path):
    f = finished | set([start%n])
    path = path + [start]
    if len(path) == n:
        check(path)
    else:
        for i in range(n*2):
            if (i % n not in f) and graph[start][i] == 1:
                clear_maze(i, f, path)
def check(path):
    #この順番に並ぶための最小
    #print(path)
    array = [i % n for i in path]
    cand = 0
    global ans
    for i in range(1,n,1):
        for j in range(i,n,1):
            if array[i-1] > array[j]:
                cand += 1
    ans = min(cand, ans)
inf = 18**2
ans = inf
for i in range(n):
    #iから始める迷路を解く
    clear_maze(i, set(), [])
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    if i % 2 == 0:
        even.append(a[i])
        odd.append(b[i])
    else:
        even.append(b[i])
        odd.append(a[i])
#odd, evenの二部グラフで、自身に辺を通さない
#a[i] <=  b[j]の時辺を通す 
graph = [[0 for __ in range(n*2)] for _ in range(n*2)]
for i in range(n):
    for j in range(n, n*2):
        if i != j % n and even[i] <= odd[j%n]:
            graph[i][j] = 1

for i in range(n,n*2):
    for j in range(n):
        if  j != i % n and odd[i % n] <= even[j]:
            graph[i][j] = 1
#グラフで一筆書きをする。パスがnになったら終わり。その順番を実現するために考える
def clear_maze(start, finished, path):
    f = finished | set([start%n])
    path = path + [start]
    if len(path) == n:
        check(path)
    else:
        for i in range(n*2):
            if (i % n not in f) and graph[start][i] == 1:
                clear_maze(i, f, path)
def check(path):
    #この順番に並ぶための最小
    #print(path)
    array = [i % n for i in path]
    cand = 0
    global ans
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if array[j] < array[j-1]:
                tmp = array[j]
                array[j] = array[j-1]
                array[j-1] = tmp
                cand += 1
    ans = min(cand, ans)
inf = 10**10
ans = inf
for i in range(n):
    #iから始める迷路を解く
    clear_maze(i, set(), [])
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**5
dp = [[INF] * (1 << n) for i in range(n)]
for i in range(n):
    dp[i][1 << i] = i

for bit_state in range(1 << n):
    cnt1 = bin(bit_state).count("1")
    for i in range(n):
        cnt0 = -1
        if not(bit_state & (1 << i)):
            continue
        for j in range(n):
            if bit_state & (1 << j):
                continue
            cnt0 += 1
            num_i = a[i] if (cnt1 - 1) % 2 == i % 2 else b[i]
            num_j = a[j] if (cnt1) % 2 == j % 2 else b[j]
            if num_i <= num_j:
                dp[j][bit_state | (1 << j)] = min(dp[j][bit_state | (1 << j)], dp[i][bit_state] + cnt0)

ans = 10**5
for i in range(n):
    ans = min(ans, dp[i][-1]) 
if ans == 10**5:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


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

INF = 10**18
dp = [[INF] * (1 << n) for i in range(n)]
for i in range(n):
    dp[i][1 << i] = i

for bit_state in range(1 << n):
    cnt1 = bin(bit_state).count("1")
    for i in range(n):
        cnt0 = -1
        if not(bit_state & (1 << i)):
            continue
        for j in range(n):
            if bit_state & (1 << j):
                continue
            cnt0 += 1
            num_i = a[i] if (cnt1 - 1) % 2 == i % 2 else b[i]
            num_j = a[j] if (cnt1) % 2 == j % 2 else b[j]
            if num_i > num_j:
                continue
            dp[j][bit_state | (1 << j)] = min(dp[j][bit_state | (1 << j)], dp[i][bit_state] + cnt0)

ans = 10**18
for i in range(n):
    ans = min(ans, dp[i][-1]) 
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


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

INF = 10**18
dp = [[INF] * (1 << n) for i in range(n)]
for i in range(n):
    dp[i][1 << i] = i

for bit_state in range(1 << n):
    for i in range(n):
        if not(bit_state & (1 << i)):
            continue
        for j in range(n):
            if bit_state & (1 << j):
                continue
            cnt1 = bin(bit_state).count("1")
            num_i = a[i] if (cnt1 - 1) % 2 == i % 2 else b[i]
            num_j = a[j] if (cnt1) % 2 == j % 2 else b[j]
            if num_i > num_j:
                continue
            cnt0 = bin((bit_state & ((1 << j) - 1)) | (1 << j)).count("0") - 1
            dp[j][bit_state | (1 << j)] = min(dp[j][bit_state | (1 << j)], dp[i][bit_state] + cnt0)

ans = 10**18
for i in range(n):
    ans = min(ans, dp[i][-1]) 
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


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

INF = 10**18
dp = [[INF] * (1 << n) for i in range(n)]
for i in range(n):
    dp[i][1 << i] = i

for bit_state in range(1 << n):
    for i in range(n):
        if not(bit_state & (1 << i)):
            continue
        for j in range(n):
            if bit_state & (1 << j):
                continue
            cnt0 = bin((bit_state & ((1 << j) - 1)) + (1 << j)).count("0") - 1
            cnt1 = bin(bit_state).count("1")
            
            num_i = a[i] if (cnt1 - 1) % 2 == i % 2 else b[i]
            num_j = a[j] if (cnt1) % 2 == j % 2 else b[j]

            if num_i <= num_j:
                dp[j][bit_state | (1 << j)] = min(dp[j][bit_state | (1 << j)], dp[i][bit_state] + cnt0)

ans = 10**18
for i in range(n):
    ans = min(ans, dp[i][-1]) 
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def is_non_decreasing():
    for i in range(len(a)-1):
        if a[i+1] < a[i]:
            return False
    return True



def search(depth):
    if is_non_decreasing():
        return True
    if depth == 0:
        return False
        
    for i in range(len(a)-1):
        a[i], b[i], a[i+1], b[i+1] = b[i+1], a[i+1], b[i], a[i]

        result = search(depth-1)

        a[i], b[i], a[i+1], b[i+1] = b[i+1], a[i+1], b[i], a[i]
        
        if result:
            return True
    
    return False
        
def iterative_deepening():
    for depth in range(0,10):
        result = search(depth)
        if result:
            print(depth)
            return
    print(-1)
    return



n = int(input())

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


iterative_deepening()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
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

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += i-bit.sum(p)
        bit.add(p, 1)
    return ans

N = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
r = 10**18
zs = [0]*N
zs2 = [(0, -1, 0)]*N
for i in range(2**N):
    for j in range(N):
        if i%2:
            zs[j] = (xs[j],(j+1)%2,j)
        else:
            zs[j] = (ys[j],j%2,j)
        i = i>>1
    zs.sort()
    ll,rr,ff=0,1,0
    for l, (z, m, j) in enumerate(zs):
        if m:
            if ll>=N:
                ff = 1
                break
            zs2[ll] = (j, z)
            ll += 2
        else:
            if rr>=N:
                ff = 1
                break
            zs2[rr] = (j, z)
            rr += 2
    if ff:
        continue
    b = 0
    for j, z in zs2:
        if b>z:
            ff = 1
            break
        b = z
    if ff:
        continue
    zs2 = [j+1 for j,_ in zs2]
    r = min(r, tento(zs2))
print(r if r != 10**18 else -1)

#    ff = 0
#    for l, (z, j,m) in enumerate(zs):
#        if (m-l)%2==0: 
#            ff = 1
#            break
#    if ff:
#        continue
#    zs = [j+1 for z,j,m in zs]

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
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
def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += i-bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

N = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
r = 10**18
for i in range(2**N):
    zs = [0]*N
    for j in range(N):
        if i%2:
            # j と偶数離れたらいい
            zs[j] = (xs[j],(j+1)%2,j)
        else:
            zs[j] = (ys[j],j%2,j)
        i = i>>1
#    print(zs)
    zs.sort()
    zs2 = [(0, -1, 0)]*N
    ll,rr=0,1
    for l, (z, m, j) in enumerate(zs):
        if m:
            if ll>=N:
                break
            zs2[ll] = (j, z, m)
            ll += 2
        else:
            if rr>=N:
                break
            zs2[rr] = (j, z, m)
            rr += 2
#    print(zs2)
    b, ff = 0, 0
    for j, z, m in zs2:
        if b>z:
            ff = 1
            break
        b = z
    if ff:
        continue
    zs2 = [j+1 for j,_,m in zs2]
    r = min(r, tento(zs2))
print(r if r != 10**18 else -1)

#    ff = 0
#    for l, (z, j,m) in enumerate(zs):
#        if (m-l)%2==0: 
#            ff = 1
#            break
#    if ff:
#        continue
#    zs = [j+1 for z,j,m in zs]

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

#a = list(map(int, input().split()))

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

dp = [[[999999,[],0] for _ in range(n)] for _ in range(2**n)]
queset = [[0 for _ in range(n)] for _ in range(2**n)]

dp[0][0][0]=0
que = [[0,0]] #[bit, num of right]
done = 0
sq2 = [2**i for i in range(20)]

while(len(que) > done):
    now = que[done]
    done +=1
    nowBits = ValueToBits(now[0],n)
    sumBits = sum(nowBits) # 既に何枚使ったか
    nowTentou = dp[now[0]][now[1]][0]
    nowCards = []
    Tentous = [0 for i in range(n)]
    for i in range(n):
        if(nowBits[i]==1):
            nowCards.append(i)
            Tentous[i] = Tentous[i-1]+1 if i>=1 else 1
        else:
            Tentous[i] = Tentous[i-1] if i>=1 else 0
    nowRight = dp[now[0]][now[1]][2]
    #if(len(nowCards)>0): print(len(nowCards),nowCards[-1],nowRight)
    for i in range(n):
        if(nowBits[i] == 0 and nowTentou<100000):
            # 右端に今加えようとしてるカード i は表か裏か
            UpDown = abs(i-sumBits)%2
            # 右端を加えた集合
            nextValue = now[0] + sq2[i]

            #nextCards = list(nowCards)
            #nextCards.append(i)
            nextRight = A[i] if UpDown==0 else B[i]
            #print(nextCards)
            if(nowRight <= nextRight):
                #print(nowRight,nextRight)
                nextTentou = nowTentou + (sumBits - Tentous[i])
                #for k in nowCards:
                #    if(k > i):
                #        nextTentou+=1
                #print(dp[nextValue][i][0] , nextTentou)
                if(dp[nextValue][i][0] > nextTentou):
                    dp[nextValue][i][0] = nextTentou
                    #dp[nextValue][i][1] = list(nextCards)
                    dp[nextValue][i][2] = nextRight
                    if(queset[nextValue][i]==0):
                        que.append([nextValue, i])
                        queset[nextValue][i]=1
                    #print(dp[nextValue][i])
#print()
ans=999999
for i in range(n):
    if(ans > dp[2**n-1][i][0]):
        ans = dp[2**n-1][i][0]
if(ans>99998):
    print(-1)
else:
    print(ans)
#print(len(que))