Leha and Function (Codeforces 841C)
Tags: Greedy, greedy

Leha like all kinds of strange things. Recently he liked the function F(n, k). Consider all possible k-element subsets of the set [1, 2, ..., n]. For subset find minimal element in it. F(n, k) — mathematical expectation of the minimal element among all k-element subsets.But only function does not interest him. He wants to do interesting things with it. Mom brought him two arrays A and B, each consists of m integers. For all i, j such that 1 ≤ i, j ≤ m the condition Ai ≥ Bj holds. Help Leha rearrange the numbers in the array A so that the sum  is maximally possible, where A' is already rearranged array.

Input: First line of input data contains single integer m (1 ≤ m ≤ 2·105) — length of arrays A and B.Next line contains m integers a1, a2, ..., am (1 ≤ ai ≤ 109) — array A.Next line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 109) — array B.

Output: Output m integers a'1, a'2, ..., a'm — array A' which is permutation of the array A.


Sample Inputs:
5
7 3 5 3 4
2 1 3 2 3

7
4 6 5 8 8 2 6
2 1 2 2 1 1 2

Sample Outputs:
4 7 3 5 3

2 6 4 5 8 8 6

Solution (Python):
""""""
''
import sys
input = sys.stdin.readline

def ceil(x):
    if x != int(x):
        x = int(x) + 1
    return x

def factorial(x, m):
    val = 1
    while x > 0:
        val = val * x % m
        x -= 1
    return val

def fact(x):
    val = 1
    while x > 0:
        val *= x
        x -= 1
    return val

def swaparr(arr, a, b):
    temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp

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

def nCr(n, k):
    if k > n - k:
        k = n - k
    res = 1
    for i in range(k):
        res = res * (n - i)
        res = res / (i + 1)
    return int(res)

def upper_bound(a, x, lo=0, hi=None):
    if hi == None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def primefs(n):
    primes = {}
    while n % 2 == 0 and n > 0:
        primes[2] = primes.get(2, 0) + 1
        n = n // 2
    for i in range(3, int(n ** 0.5) + 2, 2):
        while n % i == 0 and n > 0:
            primes[i] = primes.get(i, 0) + 1
            n = n // i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    return primes

def power(x, y, p):
    res = 1
    x = x % p
    if x == 0:
        return 0
    while y > 0:
        if y & 1 == 1:
            res = res * x % p
        y = y >> 1
        x = x * x % p
    return res

def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)

def find(x, link):
    p = x
    while p != link[p]:
        p = link[p]
    while x != p:
        nex = link[x]
        link[x] = p
        x = nex
    return p

def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        (x, y) = swap(x, y)
    if x != y:
        size[x] += size[y]
        link[y] = x

def sieve(n):
    prime = [True for i in range(n + 1)]
    (prime[0], prime[1]) = (False, False)
    p = 2
    while p * p <= n:
        if prime[p] == True:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    return prime
MAXN = int(100000.0 + 5)

def spf_sieve():
    spf[1] = 1
    for i in range(2, MAXN):
        spf[i] = i
    for i in range(4, MAXN, 2):
        spf[i] = 2
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i * i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i

def factoriazation(x):
    ret = {}
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1
        x = x // spf[x]
    return ret

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

def float_array():
    return list(map(float, input().strip().split()))

def str_array():
    return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = list(map(int, input().split()))
    l = sorted(range(n), key=b.__getitem__, reverse=True)
    for (i, j) in enumerate(l):
        b[j] = a[i]
    print(*b)
if __name__ == '__main__':
    for _ in range(1):
        solve()

Solution (Python):
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 = sorted(bi, key=lambda x: x[0])
a = sorted(a, key=lambda x: -x)
ans = [0 for i in range(n)]
for i in range(n):
    ans[bi[i][1]] = a[i]
print(' '.join([str(i) for i in ans]))

Solution (Python):
n = int(input())
A = list(map(int, input().split(' ')))
A_ = [0] * n
B = list(map(int, input().split(' ')))
for i in range(n):
    B[i] = (B[i], i)
B.sort(key=lambda x: x[0])
A.sort(key=lambda x: -x)
for i in range(n):
    A_[B[i][1]] = A[i]
print(' '.join(map(str, A_)))