Fişierul intrare/ieşire:pisi.in, pisi.outSursăLot Seniori Deva, 2019, baraj 1
AutorEugenie Daniel PosdarascuAdăugată deTincaMateiTinca Matei TincaMatei
Timp execuţie pe test4 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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:

  1. Pufoşenie sau scorul genetic: cât de pufoasă este blana pisicii;
  2. Fotogenicitate sau instinctul artistic: cât de fotogenică este pisicuţa;
  3. 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

SubtaskPunctajConstrâ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.inpisi.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 1Concurentul 2Concurentul 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?