Awards For Contestants

题意翻译

translated by @[RebelAlliance](https://www.luogu.org/space/show?uid=92461) ------------ ### 题目描述 Alexey最近为从Berland来的学生举办了一场编程测试,有 $n$ 个学生参加了测试,第 $i$ 个学生做出了 $a_{i}$ 道题。 现在他想授予一些学生文凭。Alexey可以授予学生三个不同学位的文凭。每个学生要么被授予一个学位的文凭,要么不被授予文凭。令 $cnt_{x}$ 表示被授予学位 $x$ 的文凭的学生数量。其满足一下条件: * 对任意 $x$ $( 1 \leqslant x \leqslant 3 )$,满足 $cnt_{x} > 0$ * 对任意两个学位 $x$ 和 $y$,满足 $cnt_{x} \leqslant 2cnt_{y}$ 当然,有很多种方法分发学位。令 $b_{i}$ 代表第 $i$ 个学生将获得文凭的学位(如果学生不会获得任何文凭则为 $-1$)。同时对任意的 $x$ $( 1 \leqslant x \leqslant 3 )$ 定义 $c_{x}$ 为所有获得学位 $x$ 的文凭的学生中做出最多题的学生做出的题目数量,$d_{x}$ 为所有获得学位 $x$ 的文凭的学生中做出最少题的学生做出的题目数量。Alexey想通过以下规则分发文凭: 1. 如果学生 $i$ 比学生 $j$ 做出了更多题目,那么他被授予的文凭不能比学生 $j$ 的差(不可能学生 $j$ 有文凭而学生 $i$ 没有,同时他们都有文凭但 $b_{j} < b_{i}$ 的情况也不会发生) 2. $d_{1} - c_{2}$ 取能取到的最大值 3. 在所有满足上一条的情况中,$d_{2} - c_{3}$ 取能取到的最大值 4. 在所有满足上一条的情况中,$d_{3} - c_{-1}$ 取能取到的最大值( $c_{-1}$ 为所有没有获得文凭的学生中做出最多题的学生做出的题目数量,如果所有学生都有文凭则为 $0$ ) 帮助Alexey找到一种授予文凭的方法! ### 输入格式 第一行包括一个整数 $n$ $( 3 \leqslant n \leqslant 3000 )$ 第二行包括 $n$ 个整数 $a_{1}, a_{2},…, a_{n} ( 1 \leqslant a_{i} \leqslant 5000 ) $ ### 输出格式 输出 $n$ 个数,第 $i$ 个数为第 $i$ 个学生被授予的学位(如果没有则为 $-1$ ) 如果有多组解,输出任意一组。保证答案存在。

题目描述

Alexey recently held a programming contest for students from Berland. $ n $ students participated in a contest, $ i $ -th of them solved $ a_{i} $ problems. Now he wants to award some contestants. Alexey can award the students with diplomas of three different degrees. Each student either will receive one diploma of some degree, or won't receive any diplomas at all. Let $ cnt_{x} $ be the number of students that are awarded with diplomas of degree $ x $ ( $ 1<=x<=3 $ ). The following conditions must hold: - For each $ x $ ( $ 1<=x<=3 $ ) $ cnt_{x}&gt;0 $ ; - For any two degrees $ x $ and $ y $ $ cnt_{x}<=2·cnt_{y} $ . Of course, there are a lot of ways to distribute the diplomas. Let $ b_{i} $ be the degree of diploma $ i $ -th student will receive (or $ -1 $ if $ i $ -th student won't receive any diplomas). Also for any $ x $ such that $ 1<=x<=3 $ let $ c_{x} $ be the maximum number of problems solved by a student that receives a diploma of degree $ x $ , and $ d_{x} $ be the minimum number of problems solved by a student that receives a diploma of degree $ x $ . Alexey wants to distribute the diplomas in such a way that: 1. If student $ i $ solved more problems than student $ j $ , then he has to be awarded not worse than student $ j $ (it's impossible that student $ j $ receives a diploma and $ i $ doesn't receive any, and also it's impossible that both of them receive a diploma, but $ b_{j}&lt;b_{i} $ ); 2. $ d_{1}-c_{2} $ is maximum possible; 3. Among all ways that maximize the previous expression, $ d_{2}-c_{3} $ is maximum possible; 4. Among all ways that correspond to the two previous conditions, $ d_{3}-c_{-1} $ is maximum possible, where $ c_{-1} $ is the maximum number of problems solved by a student that doesn't receive any diploma (or $ 0 $ if each student is awarded with some diploma). Help Alexey to find a way to award the contestants!

输入输出格式

输入格式


The first line contains one integer number $ n $ ( $ 3<=n<=3000 $ ). The second line contains $ n $ integer numbers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=5000 $ ).

输出格式


Output $ n $ numbers. $ i $ -th number must be equal to the degree of diploma $ i $ -th contestant will receive (or $ -1 $ if he doesn't receive any diploma). If there are multiple optimal solutions, print any of them. It is guaranteed that the answer always exists.

输入输出样例

输入样例 #1

4
1 2 3 4

输出样例 #1

3 3 2 1 

输入样例 #2

6
1 4 3 1 1 2

输出样例 #2

-1 1 2 -1 -1 3