Problem:


Score : 600 points

Problem Statement

Given are two integer sequences of N elements each: A_1,...,A_N and B_1,...,B_N.
Determine if it is possible to do the following operation at most N-2 times (possibly zero) so that, for every integer i from 1 to N, A_i \leq B_i holds:

Choose two distinct integers x and y between 1 and N (inclusive), and swap the values of A_x and A_y.

Constraints

2 \leq N \leq 10^5

1 \leq A_i,B_i \leq 10^9

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 the objective is achievable, print Yes; if it is not, print No.

Sample Input 1

3
1 3 2
1 2 3

Sample Output 1

Yes

We should swap the values of A_2 and A_3.

Sample Input 2

3
1 2 3
2 2 2

Sample Output 2

No

Sample Input 3

6
3 1 2 6 3 4
2 2 8 3 4 3

Sample Output 3

Yes



Sample input:
3
1 3 2
1 2 3


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])

    class segtree():
        def __init__(self,base,monoid,ini):#self,モノイド,元の配列
            #ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
            #basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
            # 初期値（上限とか下限）を決定
            self.ini=ini
            #セグ木の要素数（num）および深さ（depth）を計算
            self.basesize=len(base)
            self.num,self.depth=1,1
            while self.num<self.basesize:
                self.num*=2
                self.depth+=1
            self.num-=1
            #関数（モノイド、今回はmin）を設定
            self.monoid=monoid
            #セグ木を構築
            self.treesize=self.num*2+1
            self.tree=[None]*self.treesize
            #segtree[m]以降に代入したい配列を入力していく
            for i in range(self.num, self.num+self.basesize):self.tree[i]=base[i-self.num]
            for i in range(self.num+self.basesize, self.treesize):self.tree[i]=ini
            #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
            for i in range(self.num-1,-1,-1):
                self.tree[i]=monoid(self.tree[2*i+1],self.tree[2*i+2])
        
        #条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
        def max_index(self,index_func):
            #探していく
            i=0
            while i<self.num:
                k=2*i+1
                if index_func(self.tree[k+1]):
                    i=k+1
                    continue
                if index_func(self.tree[k]):
                    i=k
                    continue
                return -1
            return i-self.num
    
        #条件を満たす(サンプルの条件はs以下になること)最小のインデックスを返す関数
        def min_index(self,index_func):
            #探していく
            i=0
            while i<self.num:
                k=2*i+1
                if index_func(self.tree[k]):
                    i=k
                    continue
                if index_func(self.tree[k+1]):
                    i=k+1
                    continue
                return -1
            return i-self.num
    
        #半開区間[lower,upper)の最小値（とか）を探す関数
        def search(self,lower,upper):
            #返り値を初期化
            ret=self.ini
            l=lower+self.num
            r=upper+self.num
            while l<r:
                if r%2==0:
                    r-=1
                    ret=self.monoid(ret,self.tree[r])
                if l%2==0:
                    ret=self.monoid(ret,self.tree[l])
                    l+=1
                l//=2
                r//=2
            return ret
    
        #base[i]をsに更新したときにセグ木全体を更新する関数
        def update(self,index,new_value):
            i=index+self.num
            self.tree[i]=new_value
            while i!=0:
                i=(i-1)//2
                temp=self.monoid(self.tree[2*i+1],self.tree[2*i+2])
                if self.tree[i]!=temp:
                    self.tree[i]=temp
                    continue
                break
    
    s=segtree([a for a,b in ab],min,10**9+1)
    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = s.max_index(lambda x:x<=b)
            if t <= i:
                print("No")
                return 0
            s.update(i, a)
            s.update(t, a)
            ab[i][0], ab[t][0] = ab[t][0], a
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = list(zip(b, a))
 
a.sort()
b.sort()
for i in range(n):
  if a[i] > b[i]:
    print('No')
    exit()

ptr, pos = {}, {}
for i in range(n):
  if i > 0 and a[i] <= b[i - 1]:
    print('Yes')
    exit()
  ptr[l[i][1]] = l[i][0]
  pos[b[i]] = i

sta, now, cnt = a[0], a[0], 1
while ptr[now] != sta:
  now = a[pos[ptr[now]]]
  cnt += 1
if cnt == n:
  print('No')
else:
  print('Yes')

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int, input().split())) 
b=list(map(int, input().split())) 
 
if (max(b) < max(a) or min(b) < min(a)):
    print ('No')
 
else :
    count = 0
    for i in range(len(a)):
        if (a[i] > b[i]):
            for j in range(len(b)):
                if (a[i] <= b[j] and a[j] <= b[i]):
                    a[i],a[j] = a[j],a[i]
                    count = count + 1
                    break
 
    for k in range(len(a)):
        if (a[i] > b[i]):
            print ('No')
    
 
    if (n-2 >= count and k+1 == len(a)):
        print ('Yes')
    else :
        print ('No')

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=0
for i in range (n):
    x=i
    m=-1
    while (x<n):
        if (a[x]<=b[i]) and ((m==-1) or (a[x]>a[(0 if m==-1 else m)])):
            m=x
        x=x+1
    if (a[m]!=a[i]):
        a[m],a[i]=a[i],a[m]
        c=c+1
r=True
for i in range(n):
    if (a[i]>b[i]): r=False
if (c<=n-2) & r:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

c=0
for i in range (n):
    x=i
    m=0
    for im in range(n):
        if (a[im]<a[m]):
            m=im
    while (x<n):
        if (a[x]<=b[i]) & (a[x]>a[m]):
            m=x
        x=x+1
    if (a[m]!=a[i]):
        a[m],a[i]=a[i],a[m]
        c=c+1
r=True
for i in range(n):
    if (a[i]>b[i]): 
   		r=False
if (c<=n-2) & r:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

A_new = sorted(A)
B_new = sorted(B)
 
for i in range(N):
    if B_new[i] >= A_new[i]:
        count2 += 1
 
for i in range(N):
    for j in range(N):
        if A[i] == A_new[j] and B[i] == B_new[j]: 
            count1 = 1
            break
        if A[i] == A_new[j] and B[i] < B_new[j]:
            break
    if count1 == 1:
        break
 
if count1 == 1 and count2 == N:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

count1 = 0
count2 = 0

AB = []
AB_new = []
A_new = sorted(A)
B_new = sorted(B)

for i in range(N):
    AB.append([A[i],B[i]])
    AB_new.append([A_new[i],B_new[i]])
    
aaa = sorted(AB, key=lambda x:(x[0],x[1]))

for i in range(N):
    if B_new[i] >= A_new[i]:
        count2 += 1

for i in range(N):
    for j in range(N):
        if aaa[i] == AB_new[j]:
            count1 = 1
            break
        if AB_new[j][0] > aaa[i][0]:
            break
    if count1 == 1:
        break

if count1 == 1 and count2 == N:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [0] * N
D = [0] * N
for i in range(N):
	if sorted(A)[i] > sorted(B)[i]:
		print("No")
		exit()
	if A[i] > B[i]:
		C[i] = 1
	D[i] = B[i] - A[i]
if sum(C) > N - 2 or sum(D) < 0:
	print("No")
	exit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter    

def calc(n, A, B):
    count = 0
    for i in range(n-1):#scanA
        #print('i=',i)#Debug
        Bi = B[i:n]
        Bimin = min(Bi)
        swapnum = i+Bi.index(Bimin)
        #print(f'Bmin = {Bimin},swapnum = {swapnum}')#Debug
        
        if A[i] > Bimin:
            print('A[i] > Bimin')#Debug
            return 'No'
        elif A[i] <= Bimin <= A[i+1] <= B[i] and i != swapnum:
            B[swapnum],B[i] = B[i],B[swapnum]
            count += 1
            #print(f'swap:{count}')
            #print(f'A:{A}')
            #print(f'B:{B}')

    
    if count > n -2 or A[n-1] > B[n-1]:
        #print('n-2 or A[n-1] > B[n-1]')
        return 'No'
    else:
        return 'Yes'

                
#main

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

#print(A)
#print(B)

pair = list(zip(A,B))
pair.sort(key=itemgetter(0))#sortA

A, B = zip(*pair)

ltA = list(A)
ltB = list(B)

#print(f'A:{ltA}')
#print(f'B:{ltB}')

#print(pair)

print(calc(n,ltA,ltB))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from collections import defaultdict

def main():
    input = sys.stdin.readline
    n = int(input())
    a = np.array(list(map(int, input().split())))
    b = np.array(list(map(int, input().split())))

    a_sort = np.sort(a)
    b_sort = np.sort(b)

    # 1. 回数関係なくそもそも不可能なやつ → no
    # 2-a. サイクルは1つだとしても，完璧じゃない組み合わせが1つ以上許容されるやつ → yes
    # 2-b. サイクルが2以上にわけられるやつ → yes

    # 1
    if (a_sort > b_sort).any():
        print('No')
        exit()

    # 2-a
    if (a_sort[1:] <= b_sort[:-1]).any():
        print('Yes')
        exit()

    # 2-b （startをとりあえず1とかにする）
    d = defaultdict(int)
    for i in range(n):
        d[a[i]] = b[i]

    from_ = 1
    count = 0
    while True:
        count += 1
        from_ = d[from_]
        if from_ == 1:
            break

    if count != n:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

import numpy as np
from collections import defaultdict
n = int(input())
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))

a_sort = np.sort(a)
b_sort = np.sort(b)

# 1. 回数関係なくそもそも不可能なやつ → no
# 2-a. サイクルは1つだとしても，完璧じゃない組み合わせが1つ以上許容されるやつ → yes
# 2-b. サイクルが2以上にわけられるやつ → yes

# 1
if (a_sort > b_sort).any():
    print('No')
    exit()

# 2-a
if (a_sort[1:] <= b_sort[:-1]).any():
    print('Yes')
    exit()

# 2-b （startをとりあえず1とかにする）
d = defaultdict(int)
for i in range(n):
    d[a[i]] = b[i]

from_ = 1
count = 0
while True:
    count += 1
    from_ = d[from_]
    if from_ == 1:
        break

if count != n:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import defaultdict
n = int(input())
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))

a_sort = np.sort(a)
b_sort = np.sort(b)

# 1. 回数関係なくそもそも不可能なやつ → no
# 2-a. サイクルは1つだとしても，完璧じゃない組み合わせが1つ以上許容されるやつ → yes
# 2-b. サイクルが2以上にわけられるやつ → yes

# 1
if (a_sort > b_sort).any():
    print('No')
    exit()

# 2-a
if (a_sort[1:] <= b_sort[:-1]).any():
    print('Yes')
    exit()

# 2-b （startをとりあえず1とかにする）
d = defaultdict(int)
for i in range(n):
    d[a[i]] = b[i]

from_ = 1
count = 0
while True:
    count += 1
    from_ = d[from_]
    if from_ == 1:
        break

if count != n:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

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

count1 = 0
count2 = 0

AB = []
AB_new = []
A_new = sorted(A)
B_new = sorted(B)

for i in range(N):
    AB.append([A[i],B[i]])
    AB_new.append([A_new[i],B_new[i]])
    
aaa = sorted(AB, key=lambda x:(x[0],x[1]))

for i in range(N):
    if B_new[i] >= A_new[i]:
        count2 += 1

for i in range(N):
    for j in range(N):
        if aaa[i] == AB_new[j]:
            count1 = 1
            break
        if AB_new[j][0] > aaa[i][0]:
            break
    if count1 == 1:
        break

if count1 == 1 and count2 == N:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

count1 = 0
count2 = 0

AB = []
AB_new = []
A_new = sorted(A)
B_new = sorted(B)

for i in range(N):
    AB.append([A[i],B[i]])
    AB_new.append([A_new[i],B_new[i]])
    
aaa = sorted(AB, key=lambda x:(x[0],x[1]))

for i in range(N):
    if B_new[i] >= A_new[i]:
        count2 += 1

for i in range(N):
    for j in range(N):
        if AB_new[i] == aaa[j]:
            count1 = 1
            break
        if AB_new[i][0] < aaa[j][0]:
            break
    if count1 == 1:
        break

if count1 == 1 and count2 == N:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N = int(input())
As = list(map(int, input().strip().split()))
Bs = list(map(int, input().strip().split()))


def swap(i, j, lis):
    temp = lis[i]
    lis[i] = lis[j]
    lis[j] = temp


def search(lis, i, most):
    ret = -1
    for j in range(i + 1, len(lis)):
        if most >= lis[j] > ret:
            ret = j
    return ret


ABs = [[As[i], Bs[i]] for i in range(N)]
ABs.sort(key=lambda x: x[1])
As = [ABs[i][0] for i in range(N)]
Bs = [ABs[i][1] for i in range(N)]

#print(As)
#print(Bs)

cnt = 0
exissw = 1
for i in range(N):
    if As[i] > Bs[i]:
        lessMostIdx = search(As, i, Bs[i])
        if lessMostIdx != -1:
            swap(i, lessMostIdx, As)
            cnt += 1
        else:
            exissw = 0
            break
        if cnt > N - 2:
            exissw = 0
            break

if exissw == 0:
    print("No")
else:
    print("Yes")
    # print(As)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().strip().split()))
Bs = list(map(int, input().strip().split()))


def swap(i, j, lis):
    temp = lis[i]
    lis[i] = lis[j]
    lis[j] = temp


def search(lis, i, most):
    ret = -1
    for j in range(i + 1, len(lis)):
        if most >= lis[j] > ret:
            ret = j
    return ret


for i in range(N):
    for j in range(i + 1, N):
        if Bs[i] > Bs[j]:
            swap(i, j, Bs)
            swap(i, j, As)

# print(As)
# print(Bs)
cnt = 0
exissw = 1
for i in range(N):
    if As[i] > Bs[i]:
        lessMostIdx = search(As, i, Bs[i])
        if lessMostIdx != -1:
            swap(i, lessMostIdx, As)
            cnt += 1
        else:
            exissw = 0
            break
        if cnt > N - 2:
            exissw = 0
            break

if exissw == 0:
    print("No")
else:
    print("Yes")
    # print(As)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
A = np.asarray(list(map(int, input().split())))
B = np.asarray(list(map(int, input().split())))
AB = np.dstack((A, B))[0]
AB = AB[np.argsort(AB[:, 1])]

flag = False
k = 0
while(not flag and k<n):
    if AB[k,0] <= AB[k,1]:
        ABd = np.delete(AB, k, 0)

        As = ABd[:, 0]

        As.sort()

        for i in range(n-1):
            if As[i] > ABd[i, 1]:
                break
        else:
            flag = True

    k += 1

if flag:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)],key=lambda x:x[1])
    num=131071

    m=num+n
    segtree=[10**9+1]*m
    for i in range(num,m):
        segtree[i] = ab[i - num][0]
    for i in range(num-1,-1,-1):
        j=2*i+1
        if j>=m:
            segtree[i]=10**9+1
        elif j+1>=m:
            segtree[i]=segtree[j]
        else:
            segtree[i] = min(segtree[j], segtree[j + 1])

    #探す
    def search(i, s):
        if i >= num:
            return i - num
        k = 2 * i + 1
        if k+2<=m:
            if segtree[k+1] <= s:
                return search(k+1, s)
        if 2*i+2<=m:
            if segtree[k] <= s:
                return search(k, s)
        return -1
    
    #更新
    def update_good(i, s):
        if segtree[i] > s:
            segtree[i] = s
            update_good((i - 1) // 2, s)
    
    def update_bad(i):
        k=(i - 1) // 2
        if i % 2 == 1:
            if m > i + 1:
                temp=min(segtree[i+1],segtree[i])
                if segtree[k]<temp:
                    segtree[k] = temp
                    update_bad(k)
            else:
                segtree[k] = segtree[i]
                update_bad(k)
        else:
            if i != 0:
                temp=min(segtree[i-1],segtree[i])
                if segtree[k]<temp:
                    segtree[k] = temp
                    update_bad(k)

    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = search(0, b)
            if t <= i:
                print("No")
                return 0
            update_good(num + i, a)
            segtree[num + t] = a
            update_bad(num + t)
            ab[i][0], ab[t][0] = ab[t][0], a
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)],key=lambda x:(x[1],x[0]))

    m=131071+n
    segtree=[10**9+1]*m
    for i in range(131071,m):
        segtree[i] = ab[i - 131071][0]
    for i in range(131070,-1,-1):
        j=2*i+1
        if j>=m:
            segtree[i]=10**9+1
        elif j+1>=m:
            segtree[i]=segtree[j]
        else:
            segtree[i] = min(segtree[j], segtree[j + 1])

    #探す
    def search(i, s):
        if i >= 131071:
            return i - 131071
        if 2*i+3<=m:
            if segtree[2 * i + 2] <= s:
                return search(2 * i + 2, s)
        if 2*i+2<=m:
            if segtree[2 * i + 1] <= s:
                return search(2 * i + 1, s)
        return -1
    
    #更新
    def update_good(i, s):
        if segtree[i] > s:
            segtree[i] = s
            update_good((i - 1) // 2, s)
    
    def update_bad(i):
        if i % 2 == 1:
            if m > i + 1:
                temp=min(segtree[i+1],segtree[i])
                if segtree[(i - 1) // 2]<temp:
                    segtree[(i - 1) // 2] = temp
                    update_bad((i - 1) // 2)
            else:
                segtree[(i - 1) // 2] = segtree[i]
                update_bad((i - 1) // 2)
        else:
            if i != 0:
                temp=min(segtree[i-1],segtree[i])
                if segtree[(i - 1) // 2]<temp:
                    segtree[(i - 1) // 2] = temp
                    update_bad((i - 1) // 2)

    cnt = 0
    for i in range(n):
        if ab[i][0] > ab[i][1]:
            s = search(0, ab[i][1])
            if s <= i:
                print("No")
                return 0
            update_good(131071 + i, ab[s][0])
            segtree[131071 + s] = ab[i][0]
            update_bad(131071 + s)
            ab[i][0], ab[s][0] = ab[s][0], ab[i][0]
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)],key=lambda x:(x[1],x[0]))

    m=131071+n
    segtree=[10**9+1]*m
    #print(ab)
    for i in range(131071,m):
        segtree[i] = ab[i - 131071][0]
    for i in range(131070,-1,-1):
        j=2*i+1
        if j>=m:
            segtree[i]=10**9+1
        elif j+1>=m:
            segtree[i]=segtree[j]
        else:
            segtree[i] = min(segtree[j], segtree[j + 1])

    #探す
    def search(i, s):
        if i >= 131071:
            return i - 131071
        if 2*i+3<=m:
            if segtree[2 * i + 2] <= s:
                return search(2 * i + 2, s)
        if 2*i+2<=m:
            if segtree[2 * i + 1] <= s:
                return search(2 * i + 1, s)
        return -1
    
    #更新
    def update_good(i, s):
        if segtree[i] > s:
            segtree[i] = s
            update_good((i - 1) // 2, s)
    
    def update_bad(i):
        if i % 2 == 1:
            if m>i+1:
                segtree[(i - 1) // 2] = min(segtree[i+1],segtree[i])
                update_bad((i - 1) // 2)
            else:
                segtree[(i - 1) // 2] = segtree[i]
                update_bad((i - 1) // 2)
        else:
            if i!=0:
                segtree[(i - 1) // 2] = min(segtree[i-1],segtree[i])
                update_bad((i - 1) // 2)

    cnt = 0
    for i in range(n):
        if ab[i][0] > ab[i][1]:
            s = search(0, ab[i][1])
            if s <= i:
                print("No")
                return 0
            update_good(131071 + i, ab[s][0])
            segtree[131071 + s] = ab[i][0]
            update_bad(131071 + s)
            ab[i][0], ab[s][0] = ab[s][0], ab[i][0]
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
n= int(input())
a= list(map(int, input().split()))
b=list(map(int, input().split()))
ab=[[a[i],b[i]] for i in range(n)]
ab.sort(key=lambda x:x[1])
a.sort()
b.sort()
k=0
ans=True
for i in range(n):
    if a[i]>b[i]:
        ans=False
for i in range(n-1):
    if ab[0][0]>ab[0][1]:
        #print(ab)
        s = bisect.bisect_left(b,ab[0][0])
        #print(s)
        #print(b)
        if s<len(ab):
            ab[0][0]=ab[s][0]
            ab.pop(s)
            b.pop(s)
        else:
            ans=False
            break
    else:
        break
    k+=1
#print(ans)
if ans and k<n-1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

    bl = False
    for i in range(n):
        if a[i] > b[i]:
            continue
        aa = a[:i] + a[i+1:]
        bb = b[:i] + b[i+1:]
        aa.sort()
        bb.sort()
        bl = True
        for aae, bbe in zip(aa, bb):
            if aae > bbe:
                bl = False
                break

        if bl:
            break

    print("Yes" if bl else "No")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dat_a = list(map(int, input().split()))
dat_b = list(map(int, input().split()))

dat = []
for i in range(n):
    dat.append((dat_a[i], dat_b[i]))
dat.sort(key=lambda x: (x[1], x[0]))

dat_a = []
dat_b = []
for i in range(n):
    dat_a.append(dat[i][0])
    dat_b.append(dat[i][1])

can = True
count = 0
for i in range(n):
    #print(dat_a)
    #print(dat_b)
    #print("----[{0}]".format(i))

    if dat_a[i] > dat_b[i]:
        sind = -1
        snum = 999999999999
        for j in range(i+1, n):
            #print("check {0} <= {1}".format(dat_a[j], dat_b[i]))
            if dat_a[j] <= dat_b[i]:
                #print("yes")
                if sind == -1 and dat_a[j] < snum:
                    sind = j
                    snum = dat_a[j]
        if sind != -1:
            #print("find {0} <-> {1} index {2},{3}".format(dat_a[i], dat_a[sind],i, sind))
            count += 1
            dat_a[i], dat_a[sind] = dat_a[sind], dat_a[i]
        else:
            can = False

#print(count)
if can is False:
    print("No")
elif count > (n-2):
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
cir = False
ans = 'Yes'

sorta = np.sort(a)
sortb = np.sort(b)
indexa = np.argsort(a)
indexb = np.argsort(b)
index2b = np.concatenate([indexb,indexb])

#循環してるか
for i in range(n):
    if indexa.tolist() == index2b[i:i+n].tolist():
        cir = True
        break

if not cir:
    for i in range(n):
        if sorta[i] > sortb[i]:
            ans = 'No'
        break

if cir:
    ans = 'No'
    for i in range(1,n-1):
        temp = np.array(sorta.copy())
        temp[i], temp[i+1] = temp[i+1], temp[i]
        if np.all(temp <= sortb):
            ans = 'Yes'
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
AB = list(list(zip(A,B)))
AB.sort(key=lambda x: x[1])

flag = False
k = 0
while(not flag and k<n):
    if AB[k][0] <= AB[k][1]:
        ABd = AB[:k] + AB[k+1:]


        ABds = sorted(ABd, key=lambda x: x[0])

        for i in range(n-1):
            if ABds[i][0] > ABd[i][1]:
                break
        else:
            flag = True

    k += 1

if flag:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
def check(listA, listB):
    for i in range(len(listA)):
       if listA[i] > listB[i]:
           return False
    return True
    
def solution3(N, listA, listB):
    cnt = 0
    max_A = max(listA)
    max_B = max(listB)
    if max_A > max_B:
        return False
    if check(listA, listB):
    	return True   
    skip_index = []
    for i in range(len(listA)-2):
        max_A = 0
        max_B = 0
        for j in range(len(listA)):
            if j in skip_index:
                continue
            if max_A < listA[j]:
                max_index_A = j
                max_A = listA[j]
            if max_B < listB[j]:
                max_index_B = j
                max_B = listB[j]

        # swap
        temp = listA[max_index_B]
        listA[max_index_B] = max_A
        listA[max_index_A] = temp
        skip_index.append(max_index_B)
        
        if check(listA, listB):
            return True
    
    return False


# %%
N = int(input())
listA = input()
listA = [int(n) for n in listA.split(" ")]
listB = input()
listB = [int(n) for n in listB.split(" ")]

if solution3(N, listA, listB):
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
def ok(A,B):
    A_s = sorted(A)
    B_s = sorted(B)
    for i in range(len(A_s)):
        if A_s[i]>B_s[i]:
            return False
    return True

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

flag = 0
for i in range(N):
    A_p = A[:i]+A[i+1:]
    B_p = B[:i]+B[i+1:]
    if A[i]<=B[i]:
        if ok(A_p,B_p):
            flag=1
            break
        
if flag == 1:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

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

aa = sorted(a)
bb = sorted(b)

for i in range(n):
    if aa[i] > bb[i]:
        print('No')
        exit()
    if i != n-1 and max(aa) <= bb[i]:
        print('Yes')
        exit()

ab = []

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

ab = sorted(ab, key=lambda x:(x[1],x[0]))

if len(set(aa)) < n:
    print('Yes')
    exit()

from collections import defaultdict
d = defaultdict(int)

for i in range(n):
    d[aa[i]] += i

abd = [0]*n

for i in range(n):
    abd[i] = d[ab[i][0]]

q = [abd[0]]
chk = [0]*n
chk[0] = 1

while q:
    x = q.pop()
    if chk[x] == 0:
        chk[x] = 1
        q.append(abd[x])

if sum(chk) != n:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]

L = []
for i in range(N):
    L.append((A[i], B[i]))
    
L.sort(key=itemgetter(1))
for i in range(N):
    A[i] = L[i][0]
    B[i] = L[i][1]

def f(n, l, u, B):
    if u-l < 2:
        return u
    else:
        m = (u+l)//2
        if B[m] > n:
            return f(n, l, m, B)
        else:
            return f(n, m, u, B)

i = 0
cnt = 0
while cnt < N-2 and i < len(A):
    if A[i] > B[i]:
        t = f(A[i], i+1, len(A)-1, B)
        if A[i] <= B[t-1]:
            t -= 1
        temp = A[i]
        A[i] = A[t]
        A[t] = temp
        if A[t] == B[t]:
            A.pop(t)
            B.pop(t)
        cnt += 1
    else:
        i += 1
        
ans = "Yes"
for i in range(len(A)):
    if A[i] > B[i]:
        ans = "No"
        break
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
A1 = [(i,A[i]) for i in range(N)]
B1 = [(i,B[i]) for i in range(N)]
A1 = sorted(A1,key=lambda x:x[1])
B1 = sorted(B1,key=lambda x:x[1])
flag = 0
for i in range(N):
    if A1[i][1]>B1[i][1]:
        flag = 1
        break
if flag==1:
    judge = "No"
else:
    for i in range(N):
        if A1[i][0]==B1[i][0]:
            flag = 2
            break
        ind1 = A1.index((i,A[i]))
        s,_ = B1[ind1]
        ind2 = A1.index((s,A[s]))
        t,_ = B1[ind2]
        if i==t:
            flag=2
            break
    if flag==2:
        judge = "Yes"
    else:
        judge = "No"
print(judge)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]

L = []
for i in range(N):
    L.append([A[i], B[i]])
    
L.sort(key=itemgetter(1))
for i in range(N):
    A[i] = L[i][0]
    B[i] = L[i][1]

def f(n, l, u, B):
    if u-l < 2:
        return u
    else:
        m = (u+l)//2
        if B[m] > n:
            return f(n, l, m, B)
        else:
            return f(n, m, u, B)

i = 0
cnt = 0

while cnt < N-2 and i < len(A):
    if A[i] > B[i]:
        t = f(A[i], 0, len(A)-1, B)
        if A[i] <= B[t-1]:
            t -= 1
        temp = A[i]
        A[i] = A[t]
        A[t] = temp
        if A[t] == B[t]:
            A.pop(t)
            B.pop(t)
        cnt += 1
    else:
        i += 1
        
ans = "Yes"
for i in range(len(A)):
    if A[i] > B[i]:
        ans = "No"
        break
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A, B = [], []
for i, a in enumerate(map(int,input().split())):
  A.append([a,i])
for i, b in enumerate(map(int,input().split())):
  B.append([b,A[i], i])
B.sort()

cnt = 0
for b, a, bi in B:
  minA, minA_i = min(A)
  if minA > b:
    print('No')
    exit()

  if minA_i == bi:
    A[minA_i][0] == float('inf')
  else:
    A[minA_i][0] = A[bi][0]
    A[bi][0] = float('inf')
    cnt += 1
  
  #print(minA, b, cnt)
  if cnt > N-2:
    print('No')
    exit()
  
print('Yes')

Submission status: Time Limit Exceeded

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

flag = False
k = 0
while(not flag and k<n):
    if A[k] <= B[k]:
        As = A[:k] + A[k+1:]
        Bs = B[:k] + B[k+1:]

        As.sort()
        Bs.sort()

        for i in range(n-1):
            if As[i] > Bs[i]:
                break
        else:
            flag = True

    k += 1

if flag:
    print('Yes')
else:
    print('No')