Pisi

pisi

== include(page="template/taskheader" task_id="pisi") ==

ACPC ({*The Association of Cats' Politically Correctness*}) a afirmat că _toate pisicile sunt la fel de drăgălaşe_, afirmaţie care mai mult ca sigur este falsă, ţinând cont că există şi pisici fără blană.

Poveste şi cerinţă...

Revoltaţi de această afirmaţie, organizatorii unei expoziţii de pisici s-au hotărât să organizeze şi un concurs în cadrul expoziţiei. Astfel, ei vor evalua toate cele $N$ pisici expuse, pentru a stabili odată pentru totdeauna cele mai drăgălaşe dintre ele.

h2. Date de intrare

Fiecare pisică a fost evaluată după trei criterii:

Fişierul de intrare $pisi.in$ ...

# *Pufoşenie* sau scorul genetic: cât de pufoasă este blana pisicii;
# *Fotogenicitate* sau instinctul artistic: cât de fotogenică este pisicuţa;
# *Dragoste* sau norocul în viaţă: cât de iubită este pisica de către stăpânul ei.

h2. Date de ieşire

Organizatorii expoziţiei au conceput astfel câte un clasament separat pentru fiecare dintre cele trei categorii, stabilind ordinea celor $N$ pisici în funcţie de fiecare criteriu. Cu toate acestea, acum ei doresc să creeze un clasament cumulat, care să stabilească o ordine clară şi necontestabilă a drăgălăşeniei acestora.

În fişierul de ieşire $pisi.out$ ...

Cum în multe dintre cazuri s-a dovedit că acest lucru nu este uşor de stabilit, aceştia au convenit că o pisică $i (1 ≤ i ≤ N)$ este considerată "absolut mai drăgălaşă" decât o pisică $j$ dacă pisica $i$ apare înaintea pisicii $j$ în minim două dintre cele trei clasamente individuale.

h2. Restricţii

Întrucât nu au foarte multă experienţă cu concursurile, organizatorii te roagă să îi ajuţi să determine dacă există un clasament cumulat valid şi, dacă acesta există, să-l găseşti. Un clasament este considerat valid dacă, pentru oricare două pisici $i$ şi $j$ $(1 ≤ i, j ≤ N)$, pisica $i$ apare înaintea pisicii $j$ în clasament *dacă şi numai dacă* pisica $i$ este "absolut mai drăgălaşă" decât pisica $j$.

* $... ≤ ... ≤ ...$

h2. Detalii de implementare
 
Veţi implementa funcţia cu următorul antet:
 
== code(cpp) |
std::vector<int> rank_cats(std::vector<int> p, std::vector<int> f, std::vector<int> d)
==
 
*Atenţie!* Funcţia $rank_cats$ va fi apelată *cel puţin o dată şi de cel mult 10 ori.* Cei trei vectori $p,f$ şi $d$ vor avea aceeaşi lungime şi vor reprezenta clasamentele tuturor celor $N = |p|$ pisici, conform fiecăruia dintre cele trei criterii menţionate. De exemplu, $p{~i~}$ $(0 < N)$ va reprezenta numărul de ordine al pisicii de pe locul $i + 1$ după pufoşenie. *Se garantează că fiecare dintre cei trei vectori reprezintă permutări ale numerelor de la $1$ la $N$*.
 
Pentru ca soluţia returnată să fie validă, trebuie ca lungimea vectorului returnat să fie egală cu $N$ şi ca acesta să reprezinte un clasament cumulat valid, conform cu explicaţiile din enunţ. *Dacă nu există niciun clasament valid, funcţia trebuie să returneze vectorul vid (de lungime zero).*
 
{**Din cauza limitărilor impuse de infoarena şi pentru a reproduce condiţiile din concurs, recomandăm să foloseşti template-urile de 'aici':problema/pisi?pisi.zip .**}
 
h2. Punctare
 
 
table(example). |_. Subtask |_. Punctaj |_. Constrângeri |
| 1
| 8 puncte
| 1 &le; N &le; 10
|
| 2
| 8 puncte
| 1 &le; N &le; 17
|
| 3
| 23 puncte
| 1 &le; N &le; 2.000
|
| 4
| 61 puncte
| 1 &le; N &le; 100.000
|
 
h2. Exemple

h2. Exemplu

table(example). |_. pisi.in |_. pisi.out |

| 6
3 1 6 4 5 2
1 3 4 5 6 2
3 4 2 6 1 5
| 3 1 4 6 5 2
|
| 3
3 1 2
2 3 1
1 2 3
| NO SOLUTION
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţie

Cele trei pisici expuse corespunzătoare celui de-al doilea exemplu sunt ilustrate mai jos:
 
table(pisi). |_. Concurentul 1 |_. Concurentul 2 |_. Concurentul 3 |
| !problema/pisi?pisi1.png!
| !problema/pisi?pisi2.png!
| !problema/pisi?pisi3.png!
|
 
Concurentul cu numărul 1 este mai pufos şi mai iubit decât concurentul 2, dar este mai puţin pufos şi mai puţin fotogenic decât concurentul 3. În schimb, concurentul 2 este mai fotogenic şi mai iubit decât concurentul 3.
 
În concluzie, nu putem determina un clasament cumulat al celor trei concurenţi.

...

== include(page="template/taskfooter" task_id="pisi") ==