Problem D
Triangeltal
I en klass med $N$ elever har det blivit dags för det obligatoriska momentet att hålla tal. De flesta av eleverna ser fram emot att hålla tal väldigt mycket, och kan knappt vänta på sin tur. Men först måste de delas in i tre grupper. Alla i grupp $1$ kommer sedan presentera för grupp $2$, grupp $2$ för grupp $3$, och grupp $3$ för grupp $1$.
Något som krånglar till den här gruppindelningen är att eleverna har olika ambitionsnivå. Varje elev $i$ kräver att få hålla tal inför minst $A_ i$ personer, där $A_ i$ är ett positivt heltal. Så om elev nummer $i$ exempelvis hamnar i grupp $1$, så måste grupp $2$ ha minst $A_ i$ medlemmar för att elev $i$ ska bli nöjd.
Du får givet de $N$ talen $A_ i$, och din uppgift är att avgöra om det finns ett sätt att dela in eleverna i tre grupper så att alla blir nöjda, och hitta i så fall en giltig indelning.
Indata
Den första raden innehåller ett heltal $N$ ($3 \leq N \leq 5 \cdot 10^5$).
Den andra raden innehåller $N$ heltal $A_ i$ ($1 \leq A_ i \leq N$).
Utdata
Om det inte finns en giltig indelning, skriv ut en enda rad med strängen “NO”.
Om det finns en giltig indelning, skriv först ut en rad med strängen “YES”. Skriv därefter ut en rad med en sträng $S$ bestående av tecknen $1$, $2$ och $3$. Tecknet på plats $i$ i denna sträng indikerar vilken grupp elev $i$ hamnade i. Om det finns flera lösningar kan du skriva ut vilken som helst.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$14$ |
$A_1 = A_2 = \cdots = A_ N$ |
|
$2$ |
$16$ |
$N \leq 10$ |
|
$3$ |
$11$ |
$A_ i \leq 3$ |
|
$3$ |
$23$ |
$N \leq 3000$ |
|
$4$ |
$36$ |
Inga ytterligare begränsningar |
| Sample Input 1 | Sample Output 1 |
|---|---|
10 1 3 1 3 3 2 4 1 5 2 |
YES 3313332121 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 2 2 |
NO |
