English · Original
Chinese · Translation
Formal · Original
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 _A__i_ ≥ _B__j_ 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 _a_1, _a_2, ..., _a__m_ (1 ≤ _a__i_ ≤ 109) — array _A_.
Next line contains _m_ integers _b_1, _b_2, ..., _b__m_ (1 ≤ _b__i_ ≤ 109) — array _B_.
## Output
Output _m_ integers _a_'1, _a_'2, ..., _a_'_m_ — array _A_' which is permutation of the array _A_.
[samples]
Leha 喜欢所有奇怪的事物。最近，他喜欢上了函数 #cf_span[F(n, k)]。考虑集合 #cf_span[[1, 2, ..., n]] 的所有可能的 #cf_span[k]-元素子集。对于每个子集，找出其中的最小元素。#cf_span[F(n, k)] 是所有 #cf_span[k]-元素子集中最小元素的数学期望。
但仅有一个函数并不能让他满足。他想用它做一些有趣的事情。妈妈给他带来了两个数组 #cf_span[A] 和 #cf_span[B]，每个数组都包含 #cf_span[m] 个整数。对于所有满足 #cf_span[1 ≤ i, j ≤ m] 的 #cf_span[i, j]，都有条件 #cf_span[Ai ≥ Bj] 成立。请帮助 Leha 重新排列数组 #cf_span[A] 中的数字，使得和 尽可能大，其中 #cf_span[A'] 是重新排列后的数组。
输入数据的第一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 2·105]) —— 数组 #cf_span[A] 和 #cf_span[B] 的长度。
接下来一行包含 #cf_span[m] 个整数 #cf_span[a1, a2, ..., am] (#cf_span[1 ≤ ai ≤ 109]) —— 数组 #cf_span[A]。
接下来一行包含 #cf_span[m] 个整数 #cf_span[b1, b2, ..., bm] (#cf_span[1 ≤ bi ≤ 109]) —— 数组 #cf_span[B]。
请输出 #cf_span[m] 个整数 #cf_span[a'1, a'2, ..., a'm] —— 作为数组 #cf_span[A] 的一个排列的数组 #cf_span[A']。
## Input
输入数据的第一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 2·105]) —— 数组 #cf_span[A] 和 #cf_span[B] 的长度。接下来一行包含 #cf_span[m] 个整数 #cf_span[a1, a2, ..., am] (#cf_span[1 ≤ ai ≤ 109]) —— 数组 #cf_span[A]。接下来一行包含 #cf_span[m] 个整数 #cf_span[b1, b2, ..., bm] (#cf_span[1 ≤ bi ≤ 109]) —— 数组 #cf_span[B]。
## Output
请输出 #cf_span[m] 个整数 #cf_span[a'1, a'2, ..., a'm] —— 作为数组 #cf_span[A] 的一个排列的数组 #cf_span[A']。
[samples]
**Definitions**
Let $ m \in \mathbb{Z}^+ $ be the length of arrays $ A $ and $ B $.
Let $ A = (a_1, a_2, \dots, a_m) $ and $ B = (b_1, b_2, \dots, b_m) $ be sequences of positive integers.
Let $ A' = (a'_1, a'_2, \dots, a'_m) $ be a permutation of $ A $.
**Constraints**
1. $ 1 \leq m \leq 2 \cdot 10^5 $
2. $ 1 \leq a_i, b_j \leq 10^9 $ for all $ i, j \in \{1, \dots, m\} $
3. $ \forall i,j \in \{1,\dots,m\}, \; a_i \geq b_j $
**Objective**
Maximize the sum:
$$
\sum_{i=1}^m F(a'_i, b_i)
$$
where $ F(n, k) $ denotes the mathematical expectation of the minimum element over all $ k $-element subsets of $ \{1, 2, \dots, n\} $.
**Note**:
The function $ F(n, k) $ is given by:
$$
F(n, k) = \frac{n+1}{k+1}
$$
Thus, the objective becomes:
$$
\sum_{i=1}^m \frac{a'_i + 1}{b_i + 1}
$$
To maximize this sum, assign the largest values of $ A $ to the smallest values of $ b_i + 1 $, i.e., pair the largest $ a'_i $ with the smallest $ b_i $.
API Response (JSON)
{
"problem": {
"name": "A. Leha and Function",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF840A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Leha 喜欢所有奇怪的事物。最近，他喜欢上了函数 #cf_span[F(n, k)]。考虑集合 #cf_span[[1, 2, ..., n]] 的所有可能的 #cf_span[k]-元素子集。对于每个子集，找出其中的最小元素。#cf_span[F(n, k)] 是所有 #cf_span[k]-元素子集中最小元素的数学期望。\n\n但仅有一个函数并不能让他满足。他想用它做一些有趣的事情。妈妈给他带来...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ m \\in \\mathbb{Z}^+ $ be the length of arrays $ A $ and $ B $. \nLet $ A = (a_1, a_2, \\dots, a_m) $ and $ B = (b_1, b_2, \\dots, b_m) $ be sequences of positive integers. \nLet $...",
"is_translate": false,
"language": "Formal"
}
]
}