{"problem":{"name":"C. Average Score","description":{"content":"After the educational reform Polycarp studies only two subjects at school, Safety Studies and PE (Physical Education). During the long months of the fourth term, he received _n_ marks in them. When te","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF81C"},"statements":[{"statement_type":"Markdown","content":"After the educational reform Polycarp studies only two subjects at school, Safety Studies and PE (Physical Education). During the long months of the fourth term, he received _n_ marks in them. When teachers wrote a mark in the journal, they didn't write in what subject the mark was for, they just wrote the mark.\n\nNow it's time to show the journal to his strict parents. Polycarp knows that recently at the Parent Meeting the parents were told that he received _a_ Safety Studies marks and _b_ PE marks (_a_ + _b_ = _n_). Now Polycarp wants to write a subject's name in front of each mark so that:\n\n*   there are exactly _a_ Safety Studies marks,\n*   there are exactly _b_ PE marks,\n*   the total average score in both subjects is maximum.\n\nAn average subject grade is the sum of all marks in it, divided by the number of them. Of course, the division is performed in real numbers without rounding up or down. Polycarp aims to maximize the _x_1 + _x_2, where _x_1 is the average score in the first subject (Safety Studies), and _x_2 is the average score in the second one (Physical Education).\n\n## Input\n\nThe first line contains an integer _n_ (2 ≤ _n_ ≤ 105), _n_ is the number of marks in Polycarp's Journal. The second line contains two positive integers _a_, _b_ (1 ≤ _a_, _b_ ≤ _n_ - 1, _a_ + _b_ = _n_). The third line contains a sequence of integers _t_1, _t_2, ..., _t__n_ (1 ≤ _t__i_ ≤ 5), they are Polycarp's marks.\n\n## Output\n\nPrint the sequence of integers _f_1, _f_2, ..., _f__n_, where _f__i_ (1 ≤ _f__i_ ≤ 2) is the number of a subject to which the _i_\\-th mark should be attributed. If there are several possible solutions, then print such that the sequence _f_1, _f_2, ..., _f__n_ is the smallest lexicographically.\n\nThe sequence _p_1, _p_2, ..., _p__n_ is lexicographically less than _q_1, _q_2, ..., _q__n_ if there exists such _j_ (1 ≤ _j_ ≤ _n_) that _p__i_ = _q__i_ for all 1 ≤ _i_ < _j_, аnd _p__j_ < _q__j_.\n\n[samples]\n\n## Note\n\nIn the first sample the average score in the first subject is equal to 4, and in the second one — to 4.5. The total average score is 8.5.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"教育改革后，波利卡普在学校只学习两门课程：安全教育和体育（PE）。在第四学期漫长的几个月里，他在这两门课上共获得了 #cf_span[n] 个分数。当老师在成绩单上记录分数时，并未标明该分数属于哪门课程，仅记录了分数本身。\n\n现在到了向他严格父母展示成绩单的时候了。波利卡普知道，在最近的家长会上，老师们告知家长他获得了 #cf_span[a] 个安全教育分数和 #cf_span[b] 个体育分数（#cf_span[a + b = n]）。现在波利卡普希望在每个分数前标注对应的课程名称，使得：\n\n一门课程的平均分是该课程所有分数之和除以分数个数（除法按实数进行，不四舍五入）。波利卡普的目标是最大化 #cf_span[x1 + x2]，其中 #cf_span[x1] 是第一门课程（安全教育）的平均分，#cf_span[x2] 是第二门课程（体育）的平均分。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 10^5]），#cf_span[n] 是波利卡普成绩单上的分数个数。第二行包含两个正整数 #cf_span[a, b]（#cf_span[1 ≤ a, b ≤ n - 1, a + b = n]）。第三行包含一个整数序列 #cf_span[t1, t2, ..., tn]（#cf_span[1 ≤ ti ≤ 5]），表示波利卡普的分数。\n\n请输出一个整数序列 #cf_span[f1, f2, ..., fn]，其中 #cf_span[fi]（#cf_span[1 ≤ fi ≤ 2]）表示第 #cf_span[i] 个分数应分配给的课程编号。若有多种可行方案，请输出字典序最小的序列。\n\n序列 #cf_span[p1, p2, ..., pn] 字典序小于序列 #cf_span[q1, q2, ..., qn]，当且仅当存在某个 #cf_span[j]（#cf_span[1 ≤ j ≤ n]），使得对所有 #cf_span[1 ≤ i < j] 有 #cf_span[pi = qi]，且 #cf_span[pj < qj]。\n\n在第一个样例中，第一门课程的平均分为 4，第二门课程的平均分为 4.5，总平均分为 8.5。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 10^5]），#cf_span[n] 是波利卡普成绩单上的分数个数。第二行包含两个正整数 #cf_span[a, b]（#cf_span[1 ≤ a, b ≤ n - 1, a + b = n]）。第三行包含一个整数序列 #cf_span[t1, t2, ..., tn]（#cf_span[1 ≤ ti ≤ 5]），表示波利卡普的分数。\n\n## Output\n\n请输出一个整数序列 #cf_span[f1, f2, ..., fn]，其中 #cf_span[fi]（#cf_span[1 ≤ fi ≤ 2]）表示第 #cf_span[i] 个分数应分配给的课程编号。若有多种可行方案，请输出字典序最小的序列。序列 #cf_span[p1, p2, ..., pn] 字典序小于序列 #cf_span[q1, q2, ..., qn]，当且仅当存在某个 #cf_span[j]（#cf_span[1 ≤ j ≤ n]），使得对所有 #cf_span[1 ≤ i < j] 有 #cf_span[pi = qi]，且 #cf_span[pj < qj]。\n\n[samples]\n\n## Note\n\n在第一个样例中，第一门课程的平均分为 4，第二门课程的平均分为 4.5，总平均分为 8.5。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the total number of marks.  \nLet $ a, b \\in \\mathbb{Z}^+ $ such that $ a + b = n $, where $ a $ is the number of marks assigned to Safety Studies (subject 1), and $ b $ to PE (subject 2).  \nLet $ T = (t_1, t_2, \\dots, t_n) $ be the sequence of marks, where $ t_i \\in \\{1,2,3,4,5\\} $.  \nLet $ f = (f_1, f_2, \\dots, f_n) $, where $ f_i \\in \\{1,2\\} $, denote the assignment of subject to each mark.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq a, b \\leq n-1 $, $ a + b = n $  \n3. $ 1 \\leq t_i \\leq 5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. Exactly $ a $ indices $ i $ satisfy $ f_i = 1 $; exactly $ b $ indices satisfy $ f_i = 2 $.  \n\n**Objective**  \nMaximize the sum of averages:  \n$$\nS = \\frac{\\sum_{i: f_i=1} t_i}{a} + \\frac{\\sum_{i: f_i=2} t_i}{b}\n$$  \nSubject to the constraint that among all assignments achieving the maximum $ S $, choose the lexicographically smallest sequence $ f $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF81C","tags":["greedy","math","sortings"],"sample_group":[["5\n3 2\n4 4 5 4 4","1 1 2 1 2"],["4\n2 2\n3 5 4 5","1 1 2 2"],["6\n1 5\n4 4 4 5 4 4","2 2 2 1 2 2"]],"created_at":"2026-03-03 11:00:39"}}