{"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_(_n_, _k_) — mathematical expectation of the minimal element among all _k_\\-element subsets.\n\nBut 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.\n\n## Input\n\nFirst line of input data contains single integer _m_ (1 ≤ _m_ ≤ 2·105) — length of arrays _A_ and _B_.\n\nNext line contains _m_ integers _a_1, _a_2, ..., _a__m_ (1 ≤ _a__i_ ≤ 109) — array _A_.\n\nNext line contains _m_ integers _b_1, _b_2, ..., _b__m_ (1 ≤ _b__i_ ≤ 109) — array _B_.\n\n## Output\n\nOutput _m_ integers _a_'1, _a_'2, ..., _a_'_m_ — array _A_' which is permutation of the array _A_.\n\n[samples]","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但仅有一个函数并不能让他满足。他想用它做一些有趣的事情。妈妈给他带来了两个数组 #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'] 是重新排列后的数组。\n\n输入数据的第一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 2·105]) —— 数组 #cf_span[A] 和 #cf_span[B] 的长度。\n\n接下来一行包含 #cf_span[m] 个整数 #cf_span[a1, a2, ..., am] (#cf_span[1 ≤ ai ≤ 109]) —— 数组 #cf_span[A]。\n\n接下来一行包含 #cf_span[m] 个整数 #cf_span[b1, b2, ..., bm] (#cf_span[1 ≤ bi ≤ 109]) —— 数组 #cf_span[B]。\n\n请输出 #cf_span[m] 个整数 #cf_span[a'1, a'2, ..., a'm] —— 作为数组 #cf_span[A] 的一个排列的数组 #cf_span[A']。\n\n## Input\n\n输入数据的第一行包含一个整数 #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]。\n\n## Output\n\n请输出 #cf_span[m] 个整数 #cf_span[a'1, a'2, ..., a'm] —— 作为数组 #cf_span[A] 的一个排列的数组 #cf_span[A']。\n\n[samples]","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 $ A' = (a'_1, a'_2, \\dots, a'_m) $ be a permutation of $ A $.  \n\n**Constraints**  \n1. $ 1 \\leq m \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq a_i, b_j \\leq 10^9 $ for all $ i, j \\in \\{1, \\dots, m\\} $  \n3. $ \\forall i,j \\in \\{1,\\dots,m\\}, \\; a_i \\geq b_j $  \n\n**Objective**  \nMaximize the sum:  \n$$\n\\sum_{i=1}^m F(a'_i, b_i)\n$$  \nwhere $ F(n, k) $ denotes the mathematical expectation of the minimum element over all $ k $-element subsets of $ \\{1, 2, \\dots, n\\} $.  \n\n**Note**:  \nThe function $ F(n, k) $ is given by:  \n$$\nF(n, k) = \\frac{n+1}{k+1}\n$$  \nThus, the objective becomes:  \n$$\n\\sum_{i=1}^m \\frac{a'_i + 1}{b_i + 1}\n$$  \n\nTo 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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF840A","tags":["combinatorics","greedy","math","number theory","sortings"],"sample_group":[["5\n7 3 5 3 4\n2 1 3 2 3","4 7 3 5 3"],["7\n4 6 5 8 8 2 6\n2 1 2 2 1 1 2","2 6 4 5 8 8 6"]],"created_at":"2026-03-03 11:00:39"}}