| Fişierul intrare/ieşire: | pisi.in, pisi.out | Sursă | Lot Seniori Deva, 2019, baraj 1 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Tinca Matei •TincaMatei |
| Timp execuţie pe test | 2 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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ă.
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.
Fiecare pisică a fost evaluată după trei criterii:
- 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.
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.
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.
Detalii de implementare
Veţi implementa funcţia cu următorul antet:
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, pi (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 .
Punctare
| Subtask | Punctaj | Constrângeri |
|---|---|---|
| 1 | 8 puncte | 1 ≤ N ≤ 10 |
| 2 | 8 puncte | 1 ≤ N ≤ 17 |
| 3 | 23 puncte | 1 ≤ N ≤ 2.000 |
| 4 | 61 puncte | 1 ≤ N ≤ 100.000 |
Exemple
| 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 |
Explicaţie
Cele trei pisici expuse corespunzătoare celui de-al doilea exemplu sunt ilustrate mai jos:
| Concurentul 1 | Concurentul 2 | Concurentul 3 |
|---|---|---|
| 
| 
|
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.
