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: Accepted

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

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

# ソート
c = sorted(a)
d = sorted(b)

# 必要
for i in range(n):
    if c[i]>d[i]:
        print('No')
        exit()

# 十分。同値含むケース除外も
for i in range(n-1):
    if c[i+1]<=d[i]:
        print('Yes')
        exit()

# indexのためのdict
aa = {}  # 初期a
bb = {}  # 初期b
cc = {}  # 最終a
dd = {}  # 最終b
for i in range(n):
    aa[a[i]]=i
    bb[b[i]]=i
    cc[c[i]]=i
    dd[d[i]]=i

# サイクルでグループ化
u = UnionFind(n)
for i in range(n):
    j = aa[c[dd[b[i]]]]
    u.unite(i,j)

# グループ2つ以上でOK
for i in range(n):
    if u.same(0,i)==False:
        print('Yes')
        exit()

print('No')

Submission status: Accepted

Solution code:
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 = [[AB[i][0],i] for i in range(N)]
A.sort(key=lambda x:x[0])
da = {}
for i in range(N):
    j = A[i][1]
    da[j] = i 

ans = True
i = 0
for j in range(N):
    i = da[i]
    if i == 0:
        break

A = [AB[i][0] for i in range(N)]
A.sort()
B.sort()
if j == N-1:
    ok = False
    for i in range(N-1):
        if B[i]>=A[i+1]:
            ok = True
    ans = ok

for i in range(N):
    if A[i]>B[i]:
        ans = False

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
A = [(A[i]<<18) + i for i in range(N)]
B = [(B[i]<<18) + i + (1<<17) for i in range(N)]
AA = sorted(A)
BB = sorted(B)

IA = {}
IB = {}
for i in range(N):
    IA[AA[i]] = i
    IB[BB[i]] = i

for i in range(N):
    if AA[i] > BB[i]:
        print("No")
        break
else:
    for i in range(1, N):
        if AA[i] <= BB[i-1]:
            print("Yes")
            break
    else:
        for i in range(N):
            if IA[A[i]] == IB[B[i]]:
                print("Yes")
                break
        else:
            c = 1
            i = 0
            P = [-1] * N
            for i in range(N):
                P[IA[A[i]]] = IB[B[i]]
            i = P[0]
            while i != 0:
                i = P[i]
                c += 1
            if c < N:
                print("Yes")
            else:
                print("No")

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
BA = [(b, a) for (b, a) in zip(B, A)]
BA.sort()
B, A = list(map(list, zip(*BA)))  # BA.T
AI = [(a, i) for (i, a) in enumerate(A)]
AI.sort()
C, P = list(map(list, zip(*AI)))  # AI.T

def can_divide_cycle(P):
    start = P[1]
    ncycle = 1
    cur = start
    while P[cur] != start:
        cur = P[cur]
        ncycle += 1
    return ncycle < len(P)

vld = all(c <= b for (c, b) in zip(C, B)) \
    and (can_divide_cycle(P) or any(c <= b for (c, b) in zip(C[1:], B[:-1])))
print('Yes' if vld else 'No')

Submission status: Accepted

Solution code:
def solve(n, a_list, b_list):
    a_list_s = sorted(a_list)
    b_list_s = sorted(b_list)

    # check 1
    for i in range(n):
        if a_list_s[i] > b_list_s[i]:
            return "No"

    # check 2
    for i in range(n - 1):
        if a_list_s[i + 1] <= b_list_s[i]:
            return "Yes"

    # check 3
    # do it
    # arg sort
    a_list_s_arg = dict()
    b_list_s_org = dict()
    res_list = [0] * n
    for j in range(n):
        a_list_s_arg[a_list_s[j]] = j
    for k in range(n):
        b_list_s_org[b_list[k]] = k
    for i in range(n):
        j = a_list_s_arg[a_list[i]]
        k = b_list_s_org[b_list_s[j]]
        res_list[i] = k

    i = 0
    cnt = 0
    while True:
        i = res_list[i]
        cnt += 1
        if i == 0:
            break
    if cnt == n:
        return "No"
    else:
        return "Yes"


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, [1, 3, 2], [1, 2, 3]) == "Yes"
    assert solve(3, [1, 2, 3], [2, 2, 2]) == "No"
    assert solve(6, [3, 1, 2, 6, 3, 4], [2, 2, 8, 3, 4, 3]) == "Yes"


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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
A = III()
B = III()

def index_sort(A):
    a = []
    for i,x in enumerate(A):
        a.append([i,x])
    asort = sorted(a,key=lambda x: x[1])
    return [asort[i][0] for i in range(len(a))]

A2 = sorted(A)
B2 = sorted(B)

for i in range(N):
    if A2[i]>B2[i]:
        print('No')
        exit()

Aindex = index_sort(A)
Bindex = index_sort(B)
move = [0]*N
for i in range(N):
    move[Aindex[i]] = Bindex[i]

now = 0
for i in range(N):
    if move[now]==0 and i!=N-1:
        print('Yes')
        exit()
    now = move[now]

for i in range(N-1):
    if B2[i]>=A2[i+1]:
        print('Yes')
        exit()

print('No')

Submission status: Accepted

Solution code:
import sys
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N+1):
    par[i] = i
    rnk[i] = 0
def find(x):
  if par[x] == x:
    return x
  else:
    par[x] = find(par[x])
    return par[x]
def unite(x, y):
  x = find(x)
  y = find(y)
  if x == y:
    return
  if (rnk[x] < rnk[y]):
    par[x] = y
  else:
    par[y] = x
    if(rnk[x] == rnk[y]):
      rnk[x] += 1
def same(x, y):
  return find(x) == find(y)

N = I()
a = IL()
b = IL()

par = [0 for i in range(N+1)]
rnk = [0 for i in range(N+1)]
init(N)

adata = []
bdata = []
for i in range(N):
  adata.append([a[i], i])
  bdata.append([b[i], i])
adata.sort()
bdata.sort()
#print(adata)
#print(bdata)

a.sort()
b.sort()
f = 0
for i in range(N-1):
  atmp = a[i]
  btmp = b[i]
  atmp2 = a[i + 1]
  btmp2 = b[i + 1]
  if atmp > btmp:
    print("No")
    exit()
  if atmp2 > btmp2:
    print("No")
    exit()
  if atmp2 <= btmp:
    f = 1
else:
  if f == 1:
    print("Yes")
    exit()

for i in range(N-1):
  atmp, aID = adata[i]
  btmp, bID = bdata[i]
  #print("---")
  #print(atmp,aID)
  #print(btmp,bID)
  if aID == bID:
    break
  if same(aID, bID):
    break
  else:
    unite(aID, bID)
else:
  print("No")
  exit()
print("Yes")

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array([int(x) for x in input().split()])
B = np.array([int(x) for x in input().split()])
I = B.argsort()
A = A[I]
B = B[I]
calc = max(A) <= max(B)
if not calc:
    print("No")
    exit(0)
if any(np.sort(A)[1:] <= B[:-1]):
    print('Yes')
    exit()
p = A.argsort().tolist()
x = 0
c = 0
while True:
    c += 1
    x = p[x]
    if x == 0:
        break
print("Yes" if c != N else "No")

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()
B = LI()


A, B = zip(*sorted(zip(A, B), key=lambda x:x[1]))

A_c = copy.deepcopy(A)

A = sorted(A)
B = sorted(B)

for i in range(N):
    if A[i] > B[i]:
        print("No")
        sys.exit(0)

for i in range(1,N):
    if A[i] < B[i-1]:
        print("Yes")
        sys.exit(0)

# ans = "Yes"
# for i in range(N):
#     if A[i] <= B[i]:
#         pass
#     else:
#         ans = "No"
#         break

si2i = sorted(range(len(A_c)), key=lambda x:A_c[x])
a = 0
count = 0
while True:
    a = si2i[a]
    if a == 0:
        break
    count += 1

if count <= N - 2:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque
from collections import Counter
 
N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
 
A, B = zip(*sorted(zip(A, B), key=lambda x:x[1]))
 
A_s = sorted(A)
B_s = sorted(B)
 
no = "No"
yes = "Yes"
 
for i in range(len(A_s)):
    if A_s[i] > B_s[i]:
        print(no)
        exit(0)
 
for i in range(1, len(A_s)):
    if A_s[i] < B_s[i - 1]:
        print(yes)
        exit(0)
 
si2i = sorted(range(len(A)), key=lambda x:A[x])
 
a = 0
count = 0
while True:
    a = si2i[a]
    if a == 0:
        break
    count += 1
 
if count <= N - 2:
    print(yes)
else:
    print(no)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
A_s, B_s = sorted(A), sorted(B)
if any(a > b for a, b in zip(A_s, B_s)):
    print("No")
    quit()
A_idx = [(a, i) for i, a in enumerate(A)]
A_idx.sort()
B = [B[idx] for _, idx in A_idx]
B_idx = [(b, i) for i, b in enumerate(B)]
B_idx.sort()
perm = [i for _, i in B_idx]
cycle_len = 0
used = [False] * N
for i in range(N):
    if used[i]:
        continue
    cnt = 0
    now = i
    while not used[now]:
        used[now] = True
        cnt += 1
        now = perm[now]
    cycle_len += cnt - 1
if cycle_len < N - 1:
    print("Yes")
    quit()

if all(B_idx[i][0] < A_idx[i+1][0] for i in range(N-1)):
    print("No")
else:
    print("Yes")

Submission status: Accepted

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

A = sorted(enumerate(A), key=lambda x: x[1])
B = sorted(enumerate(B), key=lambda x: x[1])

flag = False
for i in range(N):
  if A[i][1] > B[i][1]:
    print('No')
    break
  elif i > 0 and A[i][1] <= B[i-1][1]:
    flag = True
else:
  if flag:
    print('Yes')
  else:
    D = dict((a[0], b[0]) for a, b in zip(A, B))
    count = 0
    x = D[0]
    while x != 0:
      x = D[x]
      count += 1
    print('Yes' if count < N-1 else 'No')

Submission status: Accepted

Solution code:
import sys

N=int(input())

a=list(map(int,input().split()))
b=list(map(int,input().split()))
xx=[[b[i],a[i]] for i in range(N)]
xx.sort()

a=[xx[i][1] for i in range(N)]

aa=[[xx[i][1],i] for i in range(N)]
bb=[[xx[i][0],i] for i in range(N)]

aa.sort()
bb.sort()


for i in range(N):
    if aa[i][0]>bb[i][0]:
        print("No")
        sys.exit()

for i in range(N-1):
    if aa[i][0]==aa[i+1][0] or bb[i][0]==bb[i+1][0]:
        print("Yes")
        sys.exit()

for i in range(1,N):
    if aa[i][0]<=bb[i-1][0]:
        print("Yes")
        sys.exit()


dic={}
for i in range(N):
    dic[aa[i][0]]=i

inij=1
cycle=1
j=inij

while True:
    j=dic[a[j]]
    if j==inij:
        break
    cycle+=1

print("Yes" if cycle<N else "No")

Submission status: Accepted

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

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

# 必要
c = sorted(a)
d = sorted(b)
for i in range(n):
    if c[i]>d[i]:
        print('No')
        exit()

for i in range(n-1):
    if c[i+1]<=d[i]:
        print('Yes')
        exit()

for i in range(n-1):
    if c[i]==c[i+1]:
        print('Yes')
        exit()
    if d[i]==d[i+1]:
        print('Yes')
        exit()

# 理想と現実の対応
e = {}
f = {}
for i in range(n):
    e[c[i]]=d[i]
    f[a[i]]=b[i]

# 理想と現実の対応の逆
ee = {v: k for k, v in e.items()}
ff = {v: k for k, v in f.items()}

for x in a:
    if e[x]==f[x]:
        print('Yes')
        exit()

z = [0]*n
u = UnionFind(n)

g = {}
for i in range(n):
    g[a[i]]=i

for i in range(n):
    if z[i]==1:
        continue
    x = a[i]
    y = f[x]
    j = i
    while z[j]==0:
        z[j]=1
        x = ee[y]
        y = f[x]
        jj = g[x]
        u.unite(j,jj)
        j=jj

for i in range(n):
    if u.same(0,i)==False:
        print('Yes')
        exit()


print('No')

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

def solve() :
    sA, tB = zip(*sorted(zip(A, B)))
    sB = sorted(B)
    
    for i in range(N) :
        if sA[i] > sB[i] :
            return 'No'
            
    for i in range(1, N) :
        if sA[i] <= sB[i-1] :
            return 'Yes'
    
    tB = [bisect_left(sB, tB[i]) for i in range(N)]
    pos = [0] * N
    for k, v in enumerate(tB) :
        pos[v] = k
    # print(tB)
    # print(pos)
    # vの位置はpos[v]
    count = 0
    for i in range(N) :
        if pos[i] == i :
            continue
        x = pos[i]
        y = tB[i]
        pos[i], pos[y] = pos[y], pos[i]
        tB[i], tB[x] = tB[x], tB[i]
        
        count += 1
        # print(pos, tB)
    # print('swap', count)
    if count <= N - 2 :
        return 'Yes'
    else :
        return 'No'
    
print(solve())

Submission status: Accepted

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque
from collections import Counter

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

A, B = zip(*sorted(zip(A, B), key=lambda x:x[1]))

A_s = sorted(A)
B_s = sorted(B)

no = "No"
yes = "Yes"

for i in range(len(A_s)):
    if A_s[i] > B_s[i]:
        print(no)
        exit(0)

for i in range(1, len(A_s)):
    if A_s[i] < B_s[i - 1]:
        print(yes)
        exit(0)

si2i = sorted(range(len(A)), key=lambda x:A[x])

a = 0
count = 0
while True:
    a = si2i[a]
    if a == 0:
        break
    count += 1

if count <= N - 2:
    print(yes)
else:
    print(no)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--


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

    A2 = sorted(A)
    B2 = sorted(B)
    
    for i in range(0, N):
        if A2[i] > B2[i]:
            print('No')
            return

    for i in range(1, N):
        if A2[i] <= B2[i-1]:
            print('Yes')
            return
            
    B3 = sorted(map(lambda x: (x[1][1], x[0]),
                  enumerate(sorted(map(lambda x: (x[1], x[0]),
                                       enumerate(B))))))
    C = list(map(lambda x: x[1][1], sorted(zip(A, B3))))

    p = 0
    for i in range(N-1):
         p = C[p]
         if p == 0:
             print('Yes')
             return
            
    print('No')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


def main():
    class UnionFind:
        def __init__(self, n):
            # 負  : 根であることを示す。絶対値はランクを示す
            # 非負: 根でないことを示す。値は親を示す
            self.table = [-1] * n
            self.size = [1] * n
            self.group_num = n

        def root(self, x):
            if self.table[x] < 0:
                return x
            else:
                self.table[x] = self.root(self.table[x])
                return self.table[x]

        def is_same(self, x, y):
            return self.root(x) == self.root(y)

        def get_size(self, x):
            r = self.root(x)
            return self.size[r]

        def union(self, x, y):
            r1 = self.root(x)
            r2 = self.root(y)
            if r1 == r2:
                return
            # ランクの取得
            d1 = self.table[r1]
            d2 = self.table[r2]
            if d1 <= d2:
                self.table[r2] = r1
                self.size[r1] += self.size[r2]
                if d1 == d2:
                    self.table[r1] -= 1
            else:
                self.table[r1] = r2
                self.size[r2] += self.size[r1]
            self.group_num -= 1


    n = I()
    A = LI()
    B = LI()
    a_sort = sorted([(a, i) for i, a in enumerate(A)])
    b_sort = sorted([(b, i) for i, b in enumerate(B)])
    U = UnionFind(n)
    for i in range(n):
        if a_sort[i][0] > b_sort[i][0]:
            return 'No'
    for j in range(n):
        if j != 0 and a_sort[j][0] <= b_sort[j - 1][0]:
            return 'Yes'
    b_ind_to_a_ind = {}
    for i in range(n):
        b_ind_to_a_ind[b_sort[i][1]] = a_sort[i][1]
    for j in range(n):
        U.union(j, b_ind_to_a_ind[j])
    if U.group_num == 1:
        return 'No'
    else:
        return 'Yes'



print(main())

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a_ = sorted(a)
b_ = sorted(b)
f = sum(b_[i]<a_[i] for i in range(n))
if f:
    print("No")
    exit(0)
g = sum(b_[i-1]>=a_[i] for i in range(1,n))
if g:
    print("Yes")
    exit(0)
da = dict()
for i in range(n):
    da[a_[i]] = i
ca = list(map(lambda x:da[x],a))
db = dict()
for i in range(n):
    db[b_[i]] = i
cb = list(map(lambda x:db[x],b))
cb2 = [None]*n
for i in range(n):
    cb2[ca[i]] = cb[i]
cnt = 1
c = cb2[0]
while c:
    c = cb2[c]
    cnt += 1
if cnt ==  n:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


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

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)

# B でソート
idx = B.argsort()
A = A[idx]
B = B[idx]
# この位置より右にいられる
positions = np.searchsorted(B, A, side='left')

heap = [(a, -p) for p, a in enumerate(positions)]
heapq.heapify(heap)

# A を前から見てく
# 右にあるやつのうち一番小さいの使う
cnt = 0
for i in range(N):
    a = positions[i]
    if a <= i:
        continue
    cnt += 1
    while heap and -heap[0][1] < i:
        heapq.heappop(heap)
        new_a, p = heap[0]
        p *= -1
        if positions[p] != new_a:
            continue
    new_a, p = heapq.heappop(heap)
    p *= -1
    positions[i] = new_a
    positions[p] = a
    heapq.heappush(heap, (a, -p))
    # print(positions)
# print(cnt)
# print(positions)
# print(positions <= np.arange(N))
if cnt <= N - 2 and np.all(positions <= np.arange(N)):
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

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()
    
for i in range(1,n):
    if aa[i] <= bb[i-1]:
        print('Yes')
        exit()

dg = 10**10

ab = []
for i in range(n):
    ab.append(b[i]*dg+a[i])
ab.sort()

a = []
for e in ab:
    a.append(e%dg)


idx = {}
for i in range(n):
    k = bisect.bisect_left(aa,a[i])
    idx[k] = i


for i in range(n-1):
    if a[i] == aa[i]:
        print('Yes')
        exit()
    a[idx[i]] = a[i]
    k = bisect.bisect_left(aa,a[i])
    idx[k] = idx[i]

print('No')

Submission status: Accepted

Solution code:
N=int(input())
A1=[int(s) for s in input().split()]
B1=[int(s) for s in input().split()]
A2=[(A1[i],i) for i in range(N)]
B2=[(B1[i],i) for i in range(N)]
A=sorted(A2)
B=sorted(B2)
#print(A)
#print(B)
for i in range(N):
  if B[i][0]<A[i][0]:
    print("No")
    break
else:
  for i in range(N-1):
    if B[i][0]>=A[i+1][0]:
      print("Yes")
      break
  else:
    C=[(A[i][1],B[i][1]) for i in range(N)]
    C.sort()
#    print(C)
    k=0
    for i in range(N-1):
      k=C[k][1]
      if k==0:
        print("Yes")
        break
    else:
      print("No")

Submission status: Accepted

Solution code:
import numpy as np
yes, no = "Yes", "No"
n = int(input())
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
sb = np.sort(b)
sa = np.sort(a)
sbi = np.argsort(b)
sai = np.argsort(a[sbi])
if np.any(sb < sa):
    print(no)
    exit(0)

if np.any(sb[:-1] >= sa[1:]):
    print(yes)
    exit(0)

count = 1
i = 0
while True:
    j = sai[i]
    if j == 0:
        break
    i = j
    count += 1
if count == n:
    print(no)
else:
    print(yes)

Submission status: Accepted

Solution code:
from numpy import argsort
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_sorted = sorted(A)
B_sorted = sorted(B) + [0]
for i, (a, b) in enumerate(zip(A_sorted, B_sorted)):
    if a > b:
        print("No")
        exit()
for i, (a, b) in enumerate(zip(A_sorted, B_sorted)):
    if a <= B_sorted[i-1]:
        print("Yes")
        exit()

A_rank = list(argsort(argsort(A)))
B_rank = list(argsort(argsort(B)))
B_rank_inv = [2*N] * N
for i, b in enumerate(B_rank):
    B_rank_inv[b] = i
a = 0
for i in range(N-1):
    a = A_rank[B_rank_inv[a]]
    if a==0:
        print("Yes")
        exit()
print("No")

Submission status: Accepted

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

import numpy as np

N = int(readline())
A = np.array(readline().split(),np.int32)
B = np.array(readline().split(),np.int32)

# B を昇順にしておく
I = B.argsort(); B = B[I]; A = A[I]

Asorted = np.msort(A)

if (Asorted > B).any():
    print('No')
    exit()

# N-1回あればできるやつ
# 目標位置をswapできる場所があれば、達成可能

if any(Asorted[1:] <= B[:-1]):
    print('Yes')
    exit()

# この時点で、Aは相異なり、目標インデックスも1つに決まる

perm = A.argsort().tolist()

x = 0
period = 0
while True:
    period += 1
    x = perm[x]
    if x == 0:
        break

print('Yes' if period != N else 'No')

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
z = []
for i in range(n):
  z.append([x[i],y[i]])
z.sort(key = lambda x:x[1])
a = []
b = []
for i in range(n):
  a.append(z[i][0])
  b.append(z[i][1])
#print(a)
#print(b)
A = sorted(a)
B = sorted(b)
#print(A)
#print(B)
check = 1
for i in range(n):
  if A[i] > B[i]:
    check = 0
    break
for i in range(n-1):
  if A[i+1] <= B[i]:
    check *= 2
    #print(A[i],B[i+1])
    break
#print(check)
for i in range(n-1):
  if A[i] == A[i+1]:
    check *= 2
    break
  if B[i] == B[i+1]:
    check *= 2
    break
c = []
for i in range(n):
  c.append([a[i],i])
c.sort()
#print(c)
d = [-1 for _ in range(n)]
for i in range(n):
  d[c[i][1]] = i
#print(d)
count = 0
now = 0
while True:
  count += 1
  now = d[now]
  if now == 0:
    break
#print(check,count)
if check == 0:
  print('No')
elif check > 1:
  print('Yes')
elif count == n:
  print('No')
else:
  print('Yes')

Submission status: Accepted

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

class UnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            return self.table[x]

    def Unite(self,x,y): #xとyをdiff(x,y)=W で繋げる
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]


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

BA = []
for i in range(N):
    BA.append((BB[i],AA[i]))


BA.sort()
act_AA = [(A,ai) for ai,(B,A) in enumerate(BA)]

sorted_AA = sorted(act_AA)

UF = UnionFind(N)

# print(sorted_AA)

for i,(A,ai) in enumerate(sorted_AA):
    UF.Unite(i,ai)


if UF.Size(0) != N:
    for i in range(N):
        A = sorted_AA[i][0]
        B = BA[i][0]
        if A <= B:
            continue
        else:
            print("No")
            sys.exit()
    print("Yes")
else:

    for i in range(N):
        A = sorted_AA[i][0]
        B = BA[i][0]
        if A <= B:
            continue
        else:
            print("No")
            sys.exit()

    for i in range(N-1):
        A1 = sorted_AA[i][0]
        A2 = sorted_AA[i+1][0]
        B1 = BA[i][0]
        B2 = BA[i+1][0]
        if A1 <= B2 and A2 <= B1:
            print("Yes")
            sys.exit()

    print("No")

Submission status: Runtime Error

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

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(zip(B, A))
B, A = zip(*C)
D = sorted((a, i) for i, a in enumerate(A))
E, indices = zip(*D)
for e, b in zip(E, B):
  if e > b:
    print("No")
    exit()
S = {0}
now = 0
for _ in range(n-1):
  if indices[now] in S:
    print("Yes")
    exit()
  now = indices[now]
  S.add(now)
for i in range(n):
  if E[i+1] <= B[i]:
    print("Yes")
    exit()
print("No")

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline
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()
# print(a,b)
# print(ab)
for i in range(n):
    if a[i]>b[i]:
        print("No")
        exit()
for i in range(n-1):
    if ab[0][0]>ab[0][1]:
        s = bisect.bisect_left(b,ab[0][0])
        if s<len(ab):
            ab[0][0]=ab[s][0]
            ab.pop(s)
            b.pop(s)
        else:
            print("No")
            exit()
    else:
        print("No")
        exit()

print("Yes")

Submission status: Runtime Error

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]:
        s = bisect.bisect_left(b,ab[0][0])
        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: Runtime Error

Solution code:
print("Yes)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
bi = [[b[i],i] for i in range(n)]
bi.sort()
flg = 0
if len(set(b)) == n:
  for i in range(n):
    bi[i][0] = i
  bi.sort(key = lambda x:x[1])
  idc = list(zip(*bi))[0]
  cnt = 0
  plc = 0
  while True:
    plc = idc[plc]
    cnt += 1
    if plc == 0:
      break
  if cnt == n:
    flg = 1
a.sort()
b.sort()
for x,y in zip(a,b):
  if x > y:
    print("No")
    exit()
if not flg:
  print(2/0)
  print("Yes")
else:
  for i in range(1,n):
    if a[i] <= b[i-1]:
      print("Yes")
      exit()
  print("No")