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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    b = LI()
    N = 2*n
    v = [[] for i in range(N)]
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if i&1 != j&1:
                if a[i] <= a[j]:
                    v[i].append(j)
                if b[i] <= b[j]:
                    v[i+n].append(j+n)
            else:
                if a[i] <= b[j]:
                    v[i].append(j+n)
                if b[i] <= a[j]:
                    v[i+n].append(j)
    B = 1<<n
    dp = [[float("inf")]*N for i in range(B)]
    for i in range(N):
        if i < n and i&1:
            continue
        if i >= n and not (i+n)&1:
            continue
        j = i%n
        dp[1<<j][i] = 0
    bitcount = [bin(i).count("1") for i in range(B)]
    for b in range(B):
        for i in range(N):
            bi = 1<<(i%n)
            if not b&bi:
                continue
            for j in v[i]:
                bj = 1<<(j%n)
                if b&bj:
                    continue
                nb = b|bj
                count = bitcount[b&(~(bj-1))]
                nd = dp[b][i]+count
                if nd < dp[nb][j]:
                    dp[nb][j] = nd
    ans = min(dp[-1])
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

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()))

def judge(L):
    for i in range(N-1):
        if L[i]>L[i+1]:
            return False
    return True

def swap(LA,LB,i):
    LA[i],LB[i+1]=LB[i+1],LA[i]
    LA[i+1],LB[i]=LB[i],LA[i+1]

def hash(LA,LB):
    v=0
    for a in LA:
        v+=a
        v*=51
    for b in LB:
        v+=b
        v*=51
    return v

if judge(A):
    print(0)
    exit()

Q=deque()
for i in range(N-1):
    Q.append((0,i,A[:],B[:]))
ans=0
V=set()
while Q:
    d,i,LA,LB=Q.popleft()
    if i>18:
        print(-1)
        exit()
    swap(LA,LB,i)
    h=hash(LA,LB)
    if h in V:
        continue
    if judge(LA):
        print(d+1)
        exit()
    V.add(h)
    for i in range(N-1):
        Q.append((d+1,i,LA[:],LB[:]))
print(-1)
exit()

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)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N = inp()
AA = inpl()
BB = inpl()

# In[]:
# N = 3
# AA = [3, 4, 3]
# BB = [3, 2, 3]

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


n = (N+1)//2

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



# In[]:
ans = INF
for Acards in itertools.combinations(cards, n):
    Ais = sorted([(Acard[0], Acard[2]) for Acard in Acards])

    ii = set([i for A,i in Ais])
    Bis = []
    for a,b,i in cards:
        if i not in ii:
            Bis.append((b,i))
    Bis.sort()

    nums = []
    ii = []
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        nums.append(n)
        ii.append(i)

    # print(nums,ii)
    if nums != sorted(nums):
        continue
    else:
        ans = min(ans,solve(ii))


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
reds=list(map(int,input().split()))
blus=list(map(int,input().split()))
cards=[[r,b] for r,b in zip(reds,blus)]
def to_tuple(cards):
  return tuple(tuple(c) for c in cards)
def isok(cards):
  return all(c1[0]<=c2[0] for c1,c2 in zip(cards,cards[1:]))
def swapflip(cards,i):
  cards=cards.copy()
  card =cards[i].copy()
  cards[i]  =cards[i+1][::-1]
  cards[i+1]=card[::-1]
  return cards
searched={to_tuple(cards)}
q=deque()
q.append((0,cards))
for _ in range(10**8):
  t,cards=q.popleft()
  if isok(cards):
    break
  for i in range(n-1):
    if to_tuple(swapflip(cards,i)) in searched:
      continue
    searched.add(to_tuple(swapflip(cards,i)))
    q.append((t+1,swapflip(cards,i)))
  if len(q)==0:
    t=-1
    break
print(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

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

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

def Inversion(seq):
    # seqは、1,2,...,Nの順列
    N = len(seq)
    bit = BinaryIndexedTree([0] * (N+1))
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

INF = 10 ** 9
answer = INF
for I in itertools.combinations(range(N),(N+1)//2):
    J = [j for j in range(N) if j not in I]
    ODD = [(B[i] if i&1 else A[i],i) for i in I]
    EV = [(A[i] if i&1 else B[i],i) for i in J]
    ODD.sort()
    EV.sort()
    ind = [0] * N
    seq = [0] * N
    for i in range(0,N,2):
        seq[i], ind[i] = ODD[i//2]
    for i in range(1,N,2):
        seq[i], ind[i] = EV[i//2]
    if not all(x<= y for x,y in zip(seq,seq[1:])):
        continue
    ind = [x+1 for x in ind]
    n = Inversion(ind)
    if answer > n:
        answer = n

if answer == INF:
    answer = -1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import copy


def main():
    N = int(input())
    A = [int(s) for s in input().split()]
    B = [int(s) for s in input().split()]

    cards = []
    for i in range(N):
        cards.append([A[i], B[i]])

    ng_cnt = is_ok(cards)
    if ng_cnt == 0:
        print(0)
        return

    checked = set()
    queue = [(cards, 0, -1, ng_cnt)]
    while True:
        if len(queue) == 0:
            print(-1)
            return
        case = queue.pop(0)
        for i in range(N - 1):
            if i == case[2]:
                continue
            new_cards = change(case[0], i)
            # str_cards = to_string(new_cards)
            if str(new_cards) in checked:
                continue
            checked.add(str(new_cards))
            ng_cnt = is_ok(new_cards)
            if ng_cnt == 0:
                print(case[1] + 1)
                return
            if ng_cnt <= case[3]:
                queue.append((new_cards, case[1] + 1, i, ng_cnt))


def is_ok(cards):
    cnt = 0
    for i in range(len(cards) - 1):
        if cards[i][0] > cards[i + 1][0]:
            cnt += 1
    return cnt


def change(cards, i):
    cards = copy.deepcopy(cards)
    ia = cards[i + 1][1]
    ib = cards[i + 1][0]
    i2a = cards[i][1]
    i2b = cards[i][0]
    cards[i][0] = ia
    cards[i][1] = ib
    cards[i + 1][0] = i2a
    cards[i + 1][1] = i2b
    return cards


def to_string(cards):
    a = " ".join([str(c[0]) for c in cards]) + "\n"
    b = " ".join([str(c[1]) for c in cards]) + "\n"
    return a + b


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
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])
    l_even.sort()
    l_odd.sort()
    stack=deque()
    stack.append((0,0,[],[True]*N))
    kouho=[]
    while stack:
        n,index,l,f=stack.popleft()
        if index==N:
            kouho.append(l)
            if len(kouho)>500:
                break
            continue
        
        if index%2:
            C=l_even
        else:
            C=l_odd
        for a in C[:N-(N-index)//2+1]:
            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:
        for l in kouho:
            c=0
            n=0
            while True:
                f=True
                for i in range(N-1):
                    if l[i]>l[i+1]:
                        l[i],l[i+1]=l[i+1],l[i]
                        c+=1
                        f=False
                if f:
                    ans=min(ans,c)
                    break
        print(ans)
    else:
        print(-1)
    
            
    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


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 bubcnt(v):
    bit = Bit(n)
    kaisu = 0
    for i in range(0, n):
        kaisu += i - bit.sum(v[i])
        bit.add(v[i], 1)
    return kaisu


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

xxx = permutations(l,n)

for v in xxx:
    tmp = 0
    cnt = 0
    for i in range(n):
        if tmp <= c[v[i]-1][(i-v[i]+1) % 2]:
            tmp = c[v[i]-1][(i-v[i]+1) % 2]
            cnt += 1
        else:
            break
    if cnt == n:
        ans = min(ans, bubcnt(v))

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
d={}
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(n):
  if i%2==0:
    d[i]=[a[i],b[i]]
  else:
    d[i]=[b[i],a[i]]
import itertools
se=list(itertools.permutations(range(n)))
po=[]
for i in se:
  ch=list(i)
  f=1
  t=[(d[ch[j]])[int(j%2==1)] for j in range(n)]
  for j in range(1,n):
    if t[j-1]>t[j]:
      f=0
      break
  if f:
    po.append(ch)
if len(po)==0:
  print(-1)
else:
  ans=10**9
  for l in po:
    tem=0
    for i in range(n):
      tt=0
      for j in range(n):
        if l[j]==i:
          break
        else:
          if l[j]>i:
            tt+=1
      tem+=tt
    ans=min(ans,tem)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
bbn=1000000007
	
#+++++

def is_ok(ll):
	for i,next in zip(ll,ll[1:]):
		if i > next:
			return False
	return True
	
def mkhash(al,bl):
	return '_'.join([str(v) for v in al])+'__'+'_'.join([str(v) for v in bl])
	
	
def main():
	n = int(input())
	al = list(map(int, input().split()))
	bl = list(map(int, input().split()))
	if is_ok(al):
		print(0)
		return 
		
	closed_list=set()
	open_list=queue.Queue()
	open_list.put((al,bl,0))
	closed_list.add(mkhash(al,bl))
	
	while not open_list.empty():
		cc, rv, nn = open_list.get()
		for i in range(n-1):
			tcc=cc[:]
			trv=rv[:]
			tcc[i]=rv[i+1]
			tcc[i+1]=rv[i]
			trv[i]=cc[i+1]
			trv[i+1]=cc[i]
			if mkhash(tcc,trv) in closed_list:
				continue
			if is_ok(tcc):
				return nn+1
			open_list.put((tcc,trv,nn+1))
			closed_list.add(mkhash(tcc,trv))
	
	print(-1)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

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

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


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 bubcnt(v):
    bit = Bit(n)
    kaisu = 0
    for i in range(0, n):
        kaisu += i - bit.sum(v[i])
        bit.add(v[i], 1)
    return kaisu


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

xxx = permutations(l,n)

for v in xxx:
    tmp = 0
    cnt = 0
    for i in range(n):
        if tmp <= c[v[i]-1][(i-v[i]+1) % 2]:
            tmp = c[v[i]-1][(i-v[i]+1) % 2]
            cnt += 1
        else:
            break

    if cnt == n:
        ans = min(ans, bubcnt(v))

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

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()))

pre = [1<<i for i in range(n)]
bitcnt = [0]*(1<<n)
bitcnt[1] = 1
for i in range(1<<(n-1)):
    bitcnt[2*i] = bitcnt[i]
    bitcnt[2*i+1] = bitcnt[i]+1

DP = [defaultdict(lambda : float("inf")) for i in range(n)]

for i in range(n):
    DP[i][1<<i] = 0

# 枝刈り用
# 最後に選んだ数,その時点でのstateが同じものならcostが最小のものだけを残すようにした
s = defaultdict(lambda : float("inf"))
for i in range(n-1):
    nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
    for j in range(n):
        last = a[j] if (i-j)%2 == 0 else b[j]
        for state, cost in DP[j].items():
            for to in range(n):
                if state>>to&1:
                    continue
                nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                if last > nlast:
                    continue
                nstate = state|pre[to]
                ncost = cost
                ncost += bitcnt[state>>to]
                if s[(nstate, nlast)] <= ncost:
                    continue
                s[(nstate, nlast)] = ncost
                if nxt[to][nstate] > ncost:
                    nxt[to][nstate] = ncost
    DP = nxt
mask = (1<<n)-1
ans = float("inf")
for i in range(n):
    ans = min(ans, DP[i][mask])
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy


def main():
    N = int(input())
    A = [int(s) for s in input().split()]
    B = [int(s) for s in input().split()]

    cards = []
    for i in range(N):
        cards.append([A[i], B[i]])

    if is_ok(cards):
        print(0)
        return

    checked = set()
    queue = [(cards, 0, -1)]
    while True:
        if len(queue) == 0:
            print(-1)
            return
        case = queue.pop(0)
        for i in range(N - 1):
            if i == case[2]:
                continue
            new_cards = change(case[0], i)
            # str_cards = to_string(new_cards)
            if str(new_cards) in checked:
                continue
            checked.add(str(new_cards))
            if is_ok(new_cards):
                print(case[1] + 1)
                return
            queue.append((new_cards, case[1] + 1, i))


def is_ok(cards):
    for i in range(len(cards) - 1):
        if cards[i][0] > cards[i + 1][0]:
            return False
    return True


def change(cards, i):
    cards = copy.deepcopy(cards)
    ia = cards[i + 1][1]
    ib = cards[i + 1][0]
    i2a = cards[i][1]
    i2b = cards[i][0]
    cards[i][0] = ia
    cards[i][1] = ib
    cards[i + 1][0] = i2a
    cards[i + 1][1] = i2b
    return cards


def to_string(cards):
    a = " ".join([str(c[0]) for c in cards]) + "\n"
    b = " ".join([str(c[1]) for c in cards]) + "\n"
    return a + b


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_lis = list(map(int, input().split()))
b_lis = list(map(int, input().split()))
used = []
res = -1

queue = [(a_lis, b_lis, 0)]

while queue:
    cur_a_lis, cur_b_lis, l = queue.pop(0)
    
    found = True
    pre = -1
    for a in cur_a_lis:
        if a < pre:
            found = False
            break
        pre = a
    if found:
        res = l
        break
    used.append((cur_a_lis, cur_b_lis))
    for i in range(len(cur_a_lis) - 1):
        na_lis = cur_a_lis[:i] + [cur_b_lis[i + 1]] + [cur_b_lis[i]] + cur_a_lis[i + 2:]
        nb_lis = cur_b_lis[:i] + [cur_a_lis[i + 1]] + [cur_a_lis[i]] + cur_b_lis[i + 2:]
        if (na_lis, nb_lis) not in used:
            queue.append((na_lis, nb_lis, l + 1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
def iter_bit(k, LIMIT):
    v = (1 << k) - 1

    while v < LIMIT:
        yield v
        x = v & -v
        y = v + x
        v = (v & ~y) // x >> 1 | y


def solve(n, cards):
    dp = [{} for _ in range(1 << n)]
    dp[-1][0] = 0
    LIMIT = 1 << n

    for d in range(n):
        for state in iter_bit(n - d, LIMIT):
            scores = dp[state]
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                next_dp = dp[state ^ b]
                for left_num, score in scores.items():
                    if left_num > num:
                        continue
                    ns = score + curr
                    if num not in next_dp or next_dp[num] > ns:
                        next_dp[num] = ns
                k ^= b
                curr += 1

    if len(dp[0]) > 0:
        return min(dp[0].values())
    else:
        return -1


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
def sortable(m, A, B):
    if len(A) == 1:
        return 0 if m <= A[0] else -1
    t = INF
    for i in range(len(A)):
        n = A[i] if i % 2 == 0 else B[i]
        if n < m:
            continue
        x = sortable(n, B[0:i] + A[i + 1:], A[0:i] + B[i + 1:])
        if x >= 0:
            t = min(t, x + i)
    if t != INF:
        return t
    return -1


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    print(sortable(0, A, B))

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


def solve(n, a_list, b_list):
    res = 10 ** 9 + 7
    v_dict_from = dict()
    v_dict_to = dict()

    for p in product([0, 1], repeat=n):
        q = [0] * n
        position_now = list(range(n))
        r = 0

        c_list = a_list.copy()
        for i in range(n):
            if p[i] == 1:
                c_list[i] = b_list[i]
        c_list_s = list(sorted(c_list))
        for v in range(1, 51):
            v_dict_from[v] = []
            v_dict_to[v] = []
        for i in range(n):
            v_dict_from[c_list[i]].append(i)
            v_dict_to[c_list_s[i]].append(i)
        # print(v_dict_from)
        # print(v_dict_to)
        for v in range(1, 51):
            for j, k in zip(list(sorted(v_dict_from[v])), v_dict_to[v]):
                for i in range(n):
                    if k <= position_now[i] < position_now[j]:
                        q[i] += 1
                        q[j] += 1
                        position_now[i] += 1
                        r += 1
                position_now[j] = k

            d = 0
            for j in v_dict_from[v]:
                if q[j] % 2 != p[j]:
                    d += 1
            if d % 2 == 0:
                r += d // 2
            else:
                r += 10 ** 9 + 7

        res = min(res, r)
    if res < 10 ** 9 + 7:
        return res
    else:
        return -1


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    res = solve(n, a_list, b_list)
    print(res)


def test():
    assert solve(3, [3, 4, 3], [3, 2, 3]) == 1
    assert solve(2, [2, 1], [1, 2]) == -1
    assert solve(4, [1, 2, 3, 4], [5, 6, 7, 8]) == 0


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_lis = list(map(int, input().split()))
b_lis = list(map(int, input().split()))
used = []
res = -1

queue = [(a_lis, b_lis, 0)]

while queue:
    cur_a_lis, cur_b_lis, l = queue.pop(0)
    
    found = True
    pre = -1
    for a in cur_a_lis:
        if a < pre:
            found = False
            break
        pre = a
    if found:
        res = l
        break
    used.append((a_lis, b_lis))
    for i in range(len(a_lis) - 1):
        na_lis = cur_a_lis[:i] + [cur_b_lis[i + 1]] + [cur_b_lis[i]] + cur_a_lis[i + 2:]
        nb_lis = cur_b_lis[:i] + [cur_a_lis[i + 1]] + [cur_a_lis[i]] + cur_b_lis[i + 2:]
        if (na_lis, nb_lis) not in used:
            queue.append((na_lis, nb_lis, l + 1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Card_pos = list(range(1, n+1))

def num_card(id):
  if id > 0:
    return A[id - 1]
  else:
    return B[-id - 1]

def istan(Card_pos):
  past = 0
  for id in Card_pos:
    if num_card(id) < past:
      return False
    else:
      past = num_card(id)
  else:
    return True

def exc(List, num):
  Card_pos = List[::]
  Card_pos[num], Card_pos[num + 1] = -Card_pos[num + 1], -Card_pos[num]
  return Card_pos

serched = []
counter = 0
temp = [Card_pos]
import sys

if istan(Card_pos):
  print(0)
  sys.exit()

while len(temp) != 0:
#  print(temp)
  next_temp = []
  counter += 1
  for Pos in temp:
    serched.append(Pos)
    for i in range(0, n-1):
      cand = exc(Pos, i)
#      print(cand)
      if cand not in serched:
        if istan(cand):
          print(counter)
          sys.exit()
        else:
          next_temp.append(cand)
#    print(next_temp)
  else:
    temp = next_temp
else:
  print(-1)

Submission status: Time Limit Exceeded

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])
    l_even.sort()
    l_odd.sort()
    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[:N-(N-index)//2+1]:
            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:
        for l in kouho:
            c=0
            n=0
            while True:
                f=True
                for i in range(N-1):
                    if l[i]>l[i+1]:
                        l[i],l[i+1]=l[i+1],l[i]
                        c+=1
                        f=False
                if f:
                    ans=min(ans,c)
                    break
        print(ans)
    else:
        print(-1)
    
            
    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
    
dic={}
astr=""
bstr=""
for i in range(n):
    astr+=str(a[i]).zfill(2)
    bstr+=str(b[i]).zfill(2)

ab=astr+bstr
dic[ab]=0
d=deque([ab])
# print(d)
while d:
    tmp=d.popleft()
    # print(tmp)
    for i in range(n-1):
        if int(tmp[i*2:i*2+2])>int(tmp[i*2+2:i*2+4]):
            # print(int(tmp[i*2:i*2+2]),int(tmp[i*2+2:i*2+4]))
            break
    else:
        print(dic[tmp])
        quit()

    for i in range(n-1):
        a=tmp[:n*2]
        b=tmp[n*2:]
        # print(a,b)
        tmp2=a[:i*2]+b[i*2+2:i*2+4]+b[i*2:i*2+2]+a[i*2+4:]+b[:i*2]+a[i*2+2:i*2+4]+a[i*2:i*2+2]+b[i*2+4:]
        # print(tmp2)
        if not tmp2 in dic:
            dic[tmp2]=dic[tmp]+1
            d.append(tmp2)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
def sortable(m, A, B):
    if not A:
        return 0
    t = INF
    for i in range(len(A)):
        n = A[i] if i % 2 == 0 else B[i]
        if n < m:
            continue
        x = sortable(n, B[0:i] + A[i + 1:], A[0:i] + B[i + 1:])
        if x >= 0:
            t = min(t, x + i)
    if t != INF:
        return t
    return -1


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    print(sortable(0, A, B))

main()

Submission status: Time Limit Exceeded

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

C=[]
D=[]

for i in range(N):
    if i%2==0:
        C.append(A[i])
        D.append(B[i])
    else:
        C.append(B[i])
        D.append(A[i])

permutaion = list(itertools.permutations(range(1,N+1),N))



ans=10**6
for k in range(len(permutaion)):
    flag=True
    for i in range(N-1): 
        if i%2==0:
            if C[permutaion[k][i]-1]>D[permutaion[k][i+1]-1]:
                flag=False
        else:
            if D[permutaion[k][i]-1]>C[permutaion[k][i+1]-1]:
                flag=False

    if flag:
        #print(permutaion[k])
        swap=0
        for i in range(N-1):
            for j in range(i+1,N):
                if permutaion[k][i]>permutaion[k][j]:
                    swap+=1
        ans = min(ans,swap)

if ans==10**6:
    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())) 
import itertools
seq = list(itertools.permutations(range(N)))

mi = 10**9

def crate(seq):
  temp = [0]*N
  for i in range(N):
    if abs(seq[i]-i)%2 == 0:
      temp[i] = A[seq[i]]
    else:
      temp[i] = B[seq[i]]
  return temp

def hantei(AA):
  res = True
  for i in range(N-1):
    if AA[i]>AA[i+1]:
      res = False
  return res

def bubble(seq):
  com = list(itertools.combinations(seq,2))
  res  = 0
  for i in com:
    if i[0]>i[1]:
      res += 1
  return res



for i in seq:
  AA = crate(i)
  if hantei(AA):
    mi = min(mi,bubble(i))
    
if mi ==10**9:
  print(-1)
else:
  print(mi)

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
def sortable(m, A, B):
    if not A:
        return 0
    t = INF
    for i in range(len(A)):
        n = A[i] if i % 2 == 0 else B[i]
        if n < m:
            continue
        x = sortable(n, B[0:i] + A[i + 1:], A[0:i] + B[i + 1:])
        if x >= 0:
            t = min(t, x + i)
    if t != INF:
        return t
    return -1


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    print(sortable(0, A, B))

main()