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:


# unionfind木構造
# unionfindについてはここhttps://www.slideshare.net/chokudai/union-find-49066733
# グループに属するかの判定(find)や、グループ結合(union)に強い

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    ### 重み付き
    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
As  = list(map(int, input().split()))
Bs  = list(map(int, input().split()))
As_ind = [(a,i) for i,a in enumerate(As)]
Bs_ind = [(b,i) for i,b in enumerate(Bs)]
As_ind.sort()
Bs_ind.sort()



uf = UnionFind(N)
cnt = 0
for A,B in zip(As_ind,Bs_ind):
    # print(A,B)
    if A[0] > B[0]:
        print("No")
        exit()
    uf.union(A[1],B[1])


d_ans = defaultdict(int)

for i in range(N):
    root = uf.find(i)
    d_ans[root] += 1
if len(d_ans) >= 2:
    print("Yes")
else:
    # サイクルが1つの場合
    # 巡回置換は、どこかをswapするとそこでcycleが分解されるので、swapしても結果に影響がないかを判断する
    # 具体的には A_p(i+1) <= B_i になっているならば、A_pi, A_p(i+1)をswapしても結果は変わらない。それを比べる。
    for i in range(1,N):
        if As_ind[i][0] <= Bs_ind[i-1][0]:
            print("Yes")
            exit()
    print("No")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ba = sorted((y, x) for x, y in zip(a, b))
a = [x for y, x in ba]
b = [y for y, x in ba]

ap = sorted((x, i) for i, x in enumerate(a))
if any(ap[i][0] > b[i] for i in range(n)):
    print('No')
    exit()
if any(ap[i + 1][0] <= b[i] for i in range(n - 1)):
    print('Yes')
    exit()

rep = [ap[i][1] for i in range(n)]
p = 0
c = 0
while True:
    c += 1
    p = rep[p]
    if p == 0:
        break
print(['No', 'Yes'][c != n])

Submission status: Accepted

Solution code:
import numpy as np

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
index = b.argsort()
a = a[index]
sort_dict = a.argsort().tolist()
start = 0
from_ = start
count = 0
while True:
    count += 1
    from_ = sort_dict[from_]
    if from_ == start:
        break

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

Submission status: Accepted

Solution code:
import numpy as np

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をとりあえず0番目とかにする）
index = b.argsort()
a = a[index]
sort_dict = a.argsort().tolist()
from_ = 0
count = 0
while True:
    count += 1
    from_ = sort_dict[from_]
    if from_ == 0:
        break

if count != 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()))
import numpy as np
a = sorted(A)
b = sorted(B)
a = np.array(a)
b = np.array(b)
A = np.array(A)
B = np.array(B)
if (a<=b).sum()!=N:
  print('No')

else:
  bx = np.argsort(B)
  A = A[bx]
  ax = np.argsort(A)
  dic = {}
  for i,x in enumerate(ax):
    dic[x]=i
    
  m = 0
  c = 0
  while True:
    m = dic[m]
    c += 1
    
    if (m==0) and (c!=N):
      print('Yes')
      exit()
    elif (c==N):
      break
      
  judge = False
  for i in range(N-1):
    if b[i]>=a[i+1]:
      judge = True
      break
      
  if judge:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

from collections import Counter
def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n = ri()
    la = rli()
    lb = rli()
    lab = []
    for i in range(n):
        lab.append([la[i], lb[i]])

    la.sort()
    lb.sort()
    for i in range(n):
        if la[i] > lb[i]:
            print("No")
            return

    # aでsort
    lab.sort()
    # print(lab)
    for i in range(n):
        lab[i].append(i)
    # bでsort
    lab.sort(key=lambda x: x[1])
    # print(lab)
    length = 1
    fr = 0
    to = lab[0][2]
    while to != 0:
        fr = to
        to = lab[fr][2]
        length += 1
    # cycleが二つ以上ある場合
    if length < n:
        print("Yes")
        return

    # 隣どうしをswapしてcycle二つにできる場合
    for i in range(n-1):
        if lb[i] >= la[i+1]:
            print("Yes")
            return
    
    # どうしようもない場合
    print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections
import operator
import numpy

def check_cycle(i_pair):
    i_orig_sorted_dict = {i_orig: i_sort for i_orig, i_sort in i_pair}
    cycle_dict = {}
    for i_orig, i_sort in i_pair:
        i_current = i_orig
        while True:
            if not i_current in cycle_dict:
                cycle_dict[i_current] = i_orig
            else:
                break
            i_current = i_orig_sorted_dict[i_current]
    return len(numpy.unique(list(cycle_dict.values())))


N, = map(int, sys.stdin.readline().rstrip().split(" "))
As = list(map(int, sys.stdin.readline().rstrip().split(" ")))
Bs = list(map(int, sys.stdin.readline().rstrip().split(" ")))
AB_sorted = list(sorted(zip(As, Bs), key=operator.itemgetter(1)))
Bs = list(map(operator.itemgetter(1), AB_sorted))
As_original = list(map(operator.itemgetter(0), AB_sorted))
A_i_pair = [(i_orig, i_sort) for i_sort, (i_orig, value) in enumerate(sorted(enumerate(As_original), key=operator.itemgetter(1)))]
As.sort()

# print(Bs)
# print(As_original)
# print(As)

A_reserve_dict = {}
last_reserve = None
for i in range(len(As)):
    if As[i] > Bs[i]:
        print("No")
        break
else:
    # for i in range(len(As)):
    #     if As[i] == As_original[i]:  # すでに一致してる = 1回減らせる
    #         print("Yes")
    #         break
    if check_cycle(A_i_pair) >= 2:
        print("Yes")
    else:
        for i in range(len(As) - 1):
            if As[i + 1] <= Bs[i]:  # i と i+1はどちらでもいい = 1回減らせる
                print("Yes")
                break
        else:
            print("No")
exit(0)

# Fails
# 1 2 3
# 2 3 1

# Fails
# 1 2 3 4
# 3 4 2 1

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
xa = sorted([(a[i], i) for i in range(N)], key = lambda x: x[0])
xb = sorted([(b[i], i) for i in range(N)], key = lambda x: x[0])
for i in range(N):
  if xa[i][0] > xb[i][0]:
    print("No")
    exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N)
c = 0
#print(xa, xb)
f = 0
for i in range(N):
  #print((xa[i][1], xb[i][1]))
  if uf.isSameGroup(xa[i][1], xb[i][1]):
    c += 1
  uf.Unite(xa[i][1], xb[i][1])
if c >= 2:
  print("Yes")
else:
  for i in range(N - 1):
    if xa[i + 1] <= xb[i]:
      print("Yes")
      exit(0)
  print("No")

Submission status: Accepted

Solution code:
from operator import itemgetter

def solve():
    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    Cs = sorted(As)
    Ds = sorted(Bs)

    for A, B in zip(Cs, Ds):
        if A > B:
            return False

    for i in range(N-1):
        if Cs[i] <= Ds[i+1] and Cs[i+1] <= Ds[i]:
            return True

    ABs = [(A, B) for A, B in zip(As, Bs)]
    ABs.sort(key=itemgetter(1))

    As = [A for A, B in ABs]
    Bs = [B for A, B in ABs]
    iAs = list(range(N))
    iAs.sort(key=lambda iA: As[iA])
    convs = dict()
    for i in range(N):
        convs[As[iAs[i]]] = i

    for i in range(N-2):
        if As[i] <= Bs[i]:
            return True
        X, Y = As[i], As[iAs[i]]
        As[i], As[iAs[i]] = As[iAs[i]], As[i]
        iAs[convs[X]], iAs[convs[Y]] = iAs[convs[Y]], iAs[convs[X]]

    if As[N-2] <= Bs[N-2] and As[N-1] <= Bs[N-1]:
        return True
    else:
        return False

if solve():
    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()))

def count_loop(start, idx_map):
    count = 0
    idx = start
    while True:
        idx = idx_map[idx]
        count += 1
        if idx == 0:
            break
    return count

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

check_1 = all(A[i] <= B[i] for i in range(N))
check_2 = any(A[i + 1] <= B[i] for i in range(N - 1))
check_3 = count_loop(0, idx_map) <= N - 2
print("Yes" if (check_1 and (check_2 or check_3)) else "No")

Submission status: Accepted

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

def count_loop(start, idx_map):
    count = 1
    idx = start
    while True:
        idx = idx_map[idx]
        count += 1
        if idx == 0:
            break
    return count

X = list(zip(A, B))
X.sort(key=lambda x: x[1])

C = sorted((x[0], i) for i, x in enumerate(X))
idx_map = [C[i][1] for i in range(N)]
A = sorted(A)
B = sorted(B)

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

if any(A[i + 1] <= B[i] for i in range(N - 1)):
    print("Yes")
    exit()

if count_loop(0, idx_map) < N:
    print("Yes")
    exit()

print("No")

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

for a, b in zip(sorted(A), sorted(B)):
    if a > b:
        print('No')
        exit()

# Bの昇順でAを並び替え
BA = list(zip(A, B))
BA.sort()

AI = [(a, i) for i, (_, a) in enumerate(BA)]
AI.sort()

tree = UnionFind(N)
for nessIndex, (_, originalIndex) in enumerate(AI):
    tree.union(nessIndex, originalIndex)

V = set()
for i in range(N):
    V.add(tree.root(i))

if len(V) > 1:  # サイクルが複数の場合
    print('Yes')
    exit()

if any(a <= b for a, b in zip(sorted(A)[1:], sorted(B)[:-1])):
    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()))
X=list(zip(A,B))
X.sort(lambda x:x[1])

C=[(x[0],i) for i,x in enumerate(X)]
C.sort()
perm=[C[i][1] for i in range(n)]

A.sort()
B.sort()

if(any(A[i]>B[i] for i in range(n))):
    print("No")
    exit()

if(any(A[i+1]<=B[i] for i in range(n-1))):
    print("Yes")
    exit()

p=0
cnt=0
while(True):
    cnt+=1
    p=perm[p]
    if(p==0): break
print("Yes" if(cnt<n) else "No")

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

import numpy as np

def main():
    n = ni()
    a = np.array(list(li()))
    b = np.array(list(li()))

    idx = b.argsort().tolist()

    b = b[idx]
    a = a[idx]

    # N-1回以内なら達成可能か判定
    a_sorted = np.msort(a)
    if any(a_sorted > b):
        print('No')
        return

    # N-2回以内で達成可能か判定
    # 置換サイクルが複数あるなら可能
    if any(a_sorted[1:] <= b[:-1]):
        print('Yes')
        return

    perm = a.argsort().tolist()
    x = 0
    period = 0
    for i in range(n):
        period += 1
        x = perm[x]
        if x == 0:
            break

    print('Yes' if period < n else 'No')
    return

if __name__ == "__main__":
    main()

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 = [0] * N
for i, (_, idx) in enumerate(B_idx):
    perm[idx] = i
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:
class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    X = sorted(zip(B, A))
    A = list(map(lambda x: x[1], X))
    B = list(map(lambda x: x[0], X))
    sortedA = sorted(A)
    for i in range(N):
        if sortedA[i] > B[i]:
            print("No")
            return
    for i in range(N-1):
        if sortedA[i+1] <= B[i]:
            print("Yes")
            return
    uft = UnionFindTree(N)
    desired_pos = {sortedA[i]: i for i in range(N)}
    for i in range(N):
        uft.unite(i, desired_pos[A[i]])
    if len(uft.groups()) == 1:
        print("No")
    else:
        print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools

def sRaw():
    return input().rstrip("\r")

def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    
def ZAlgo(s):
    l = len(s)
    A = [0]*l
    i =1
    j =0
    A[0]=l
    while i<l:
        while i+j<l and s[j] == s[i+j]:
            j+=1
        if j==0:
            i+=1
            continue
        A[i]=j
        k=1
        while (i+k<l) and (k+A[k]<j):
            A[i+k] =A[k]
            k+=1
        i+=k
        j-=k
    return A


DIV = 998244353

def main():
    N = iRaw()
    As = isRaw()
    Bs = isRaw()
    BAs = list(zip(Bs,As))
    BAs.sort()
    AIs = [[ba[1],idx] for idx,ba in enumerate(BAs)]
    AIs.sort()
    sAidx = [0]*len(AIs)
    for sIdx,ai in enumerate(AIs):
        a,idx = ai
        if a>BAs[sIdx][0]:
            return "No"
        sAidx[idx]=sIdx
    cycleSize = 0
    curIdx = 0
    visited = [0]*len(AIs)
    while visited[curIdx]==0:
        visited[curIdx]=1
        cycleSize +=1
        curIdx = sAidx[curIdx]
    if cycleSize < N:
        return "Yes"

    for idx in range(N-1):
        if AIs[idx+1][0]<=BAs[idx][0]:
            return "Yes"
    return "No"

if __name__ == "__main__":
    print(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


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_index = sorted(range(n), key=lambda x:A[x])
b_sort_index = sorted(range(n), key=lambda x: B[x])
flag = 0
U = UnionFind(n)
for i in range(n):
    if A[a_sort_index[i]] > B[b_sort_index[i]]:
        print('No')
        break
    elif i != 0 and A[a_sort_index[i]] <= B[b_sort_index[i - 1]]:
        flag = 1
    U.union(a_sort_index[i], b_sort_index[i])
else:
    if U.group_num == 1 and not flag:
        print('No')
    else:
        print('Yes')

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


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


def main():
    n = I()
    A = LI()
    B = LI()
    a_sort_index = sorted(range(n), key=lambda x:A[x])
    b_sort_index = sorted(range(n), key=lambda x: B[x])
    flag = 0
    U = UnionFind(n)
    for i in range(n):
        if A[a_sort_index[i]] > B[b_sort_index[i]]:
            return 'No'
        elif i != 0 and A[a_sort_index[i]] <= B[b_sort_index[i - 1]]:
            flag = 1
        U.union(a_sort_index[i], b_sort_index[i])
    if U.group_num == 1 and not flag:
        return 'No'
    else:
        return 'Yes'



print(main())

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]

ab=[[a[i],b[i]] for i in range(n)]
ab.sort(key=lambda x:x[1])

a=[ab[i][0] for i  in range(n)]
b=[ab[i][1] for i  in range(n)]

ai=[[a[i],i] for i in range(n)]
ai.sort(key=lambda x:x[0])

flag1=True
for i in range(n):
  if ai[i][0]>b[i]:
    flag1=False
    break
    
idx=ai[0][1]
cnt=0
while idx!=0:
  idx=ai[idx][1]
  cnt+=1

if cnt==n-1:
  flag2=False
  for i in range(n-1):
    if b[i]>=ai[i+1][0]:
      flag2=True
      break
else:
  flag2=True
  
if flag1 and flag2:
  ans='Yes'
else:
  ans='No'
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

AB = [(A[i],B[i]) for i in range(N)]
AB.sort(key=lambda x: x[1])

A = [AB[i][0] for i in range(N)]
B = [AB[i][1] for i in range(N)]

AI = [(AB[i][0], i) for i in range(N)]

A.sort()
AI.sort(key=lambda x:x[0])

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

idx = AI[0][1]
cnt = 1
while idx != 0:
    idx = AI[idx][1]
    cnt += 1

if cnt == N:
    flag2 = False
    for i in range(N-1):
        if B[i] >= A[i+1]:
            flag2 = True
            break
else:
    flag2 = True

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

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    bb = list(map(int, input().split()))
    aaii = [[a, i] for i, a in enumerate(aa)]
    bbii = [[b, i] for i, b in enumerate(bb)]
    aaii.sort()
    bbii.sort()
    #print(aaii)
    #print(bbii)
    aibi = []
    swap = False
    for i in range(n):
        a, ai = aaii[i]
        b, bi = bbii[i]
        aibi.append([ai, bi])
        if a > b:
            print("No")
            exit()
        if swap: continue
        if i + 1 < n and aaii[i + 1][0] <= b:
            swap = True
    aibi.sort(key=itemgetter(1))
    #print(aibi)
    if swap:
        print("Yes")
        exit()
    now = 0
    cnt = 0
    while 1:
        now = aibi[now][0]
        cnt += 1
        if now == 0:
            if cnt == n:
                print("No")
            else:
                print("Yes")
            break

main()

Submission status: Accepted

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

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

lst.sort(key=lambda x: x[0])
lst.sort(key=lambda x: x[1])

sorted_a = []
sorted_b = []
for i in range(n):
    sorted_a.append(lst[i][0])
    sorted_b.append(lst[i][1])

ind = list(range(n))
lst = []
for i in range(n):
    lsti = [ind[i], sorted_a[i]]
    lst.append(lsti)
lst.sort(key=lambda x: x[1])

sorted_ind = []
shoujun_a = []
for i in range(n):
    sorted_ind.append(lst[i][0])
    shoujun_a.append(lst[i][1])

for i in range(n):
    if sorted_b[i] < shoujun_a[i]:
        print('No')
        exit()

lenghth = 1
start = 0
i = 0
while start != sorted_ind[i]:
    lenghth += 1
    i = sorted_ind[i]

if lenghth != n:
    print('Yes')
else:
    for i in range(n-1):
        if sorted_b[i] >= shoujun_a[i+1]:
            print('Yes')
            exit()
    print('No')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    X=list(zip(A,B))
    X.sort(lambda x:x[1])

    C=[(x[0],i) for i,x in enumerate(X)]
    C.sort()
    perm=[C[i][1] for i in range(n)]

    A.sort()
    B.sort()

    # A <= B を満たしていなければ不可能
    if(any(A[i]>B[i] for i in range(n))):
        print("No")
        return

    # 自由度が1つあれば可能
    if(any(A[i+1]<=B[i] for i in range(n-1))):
        print("Yes")
        return

    # permのYoung図が[n]かどうかで判断
    p=0
    cnt=0
    while(True):
        cnt+=1
        p=perm[p]
        if(p==0): break
    print("Yes" if(cnt<n) else "No")
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    X=list(zip(A,B))
    X.sort(lambda x:x[1])

    C=[(x[0],i) for i,x in enumerate(X)]
    C.sort()
    perm=[C[i][1] for i in range(n)]

    A.sort()
    B.sort()

    # A <= B を満たしていなければ不可能
    if(any(A[i]>B[i] for i in range(n))):
        print("No")
        return

    # 自由度が1つあれば可能
    if(any(A[i+1]<=B[i] for i in range(n-1))):
        print("Yes")
        return

    # permのYoung図が[n]かどうかで判断
    cnt=0
    visited=[0]*n
    def dfs(v)->int:
        if(visited[v]): return 0
        visited[v]=1
        stack=[v]
        cnt=0
        while(stack):
            cnt+=1
            v=stack.pop()
            nv=perm[v]
            if(visited[nv]):break
            visited[nv]=1
            stack.append(nv)
        return cnt

    print("Yes" if(dfs(0)<n) else "No")
resolve()