pisi

Pisi

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

Poveste şi cerinţă...

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ă.

h2. Date de intrare

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.

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

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

h2. Date de ieşire

# *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.

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

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.

h2. Restricţii

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.

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

Î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. Exemplu

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

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

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

| 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
|

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") ==