Fişierul intrare/ieşire:pswap.in, pswap.outSursăOSEPI Baraj Seniori 2
AutorBogdan PopAdăugată deMatteoalexandruMatteo Verzotti Matteoalexandru
Timp execuţie pe test5 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pswap

Eşti în anul 2121 şi vrei să configurezi o reţea de Neuralink. Ai la dispoziţie N servere, ale căror IP-uri sunt reprezentate de permutări de lungime M (ale numerelor 0, 1 ... M-1). Vrei ca reţeaua ta să fie cât de mare, dar în acelaşi timp, te temi de potenţiale probleme de securitate: dacă un hacker află unul dintre IP-uri, îi va fi uşor să găsească un IP similar. Prin urmare, dintre cele N servere pe care le ai la dispoziţie, vrei să alegi cât de multe servere pentru reţeaua ta astfel încât să nu existe două servere cu IP-uri similare. Două IP-uri sunt similare, dacă unul dintre ele poate fi obţinut din celălalt print exact o operaţie swap (o interschimbare a oricăror două elemente). De exemplu, IP-urile (0, 1, 2) şi (1, 0, 2) sunt similare, dar (0, 1, 2) şi (1, 2, 0) nu.

Protocol de interacţiune

Concurentul trebuie să implementeze o funcţie:

(C)   int solve(int N, int M, int** p);
(C++) int solve(int N, int M, std::vector< std::vector<int> > p);

Parametrii N şi M au semnificaţia din enunţ. p reprezintă o matrice cu N linii şi M coloane, linia i reprezentând cel de-al i-lea IP (o permutare de lungime M). Funcţia va întoarce numărul maxim de IP-uri nesimilare.

Din cauza limitărilor impuse de Infoarena şi pentru a reproduce condiţiile din concurs, recomandăm să foloseşti template-urile de aici.

Restricţii

  • 1 ≤ N ≤ 2500
  • 1 ≤ M ≤ 5000
  • Oricare ar fi 0 ≤ i < n, p[i] este o permutare a numerelor de la 0 la M - 1
  • Oricare ar fi 0 ≤ i, j < n, p[i] si p[j] sunt distincte

Subtask 1 (11 puncte)

  • N, M ≤ 20

Subtask 2 (30 de puncte)

  • Cel mult 20 de permutări din cele N sunt similare cu oricare alta dintre cele N
  • N ≤ 1000

Subtask 3 (36 de puncte)

  • N ≤ 300

Subtask 4 (14 puncte)

  • N ≤ 1000

Subtask 5 (9 puncte)

  • Fără restricţii suplimentare.

Exemplu

pswap.inpswap.out
3 3
0 1 2
2 1 0
1 0 2
2
5 5
0 1 2 3 4
1 0 2 3 4
0 1 2 4 3
0 4 2 3 1
4 1 2 3 0
4
6 3
0 1 2
0 2 1
1 0 2
1 2 0
2 1 0
2 0 1
3

Explicaţie

Pentru primul exemplu, alegem serverele cu IP-urile (2, 1, 0) şi (1, 0, 2). Nu putem alege serverul (0, 1, 2), deoarece IP-ul său este similar cu ale celorlalte 2.

Pentru cel de-al doilea exemplu, putem alege toate IP-urile în afară de primul.

Pentru cel de-al treilea exemplu, putem selecta IP-urile (0, 1, 2), (1, 2, 0), (2, 0, 1).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?