Assemblage de clés – Regional event 2022

Level 2

Énoncé

Une autre porte se présente, verrouillée par $N$ serrures. Votre objectif va être de déverrouiller un maximum de serrures simultanément. Cependant, toutes les clés de ces serrures ont été coupée en $P$ morceaux.

Chaque serrure et chaque partie de clé possède un type $i$. Pour ouvrir une serrure, il est donc nécessaire de reformer une clé du même type en rassemblant tous les morceaux correspondants.

Les serrures ainsi que chaque partie de clé sont ordonnées par ordre de type.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de serrures.
  • Sur la ligne suivante, un entier : P, le nombre de parties nécessaires pour composer une clé.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : serrures, le type de chaque serrure.
  • Sur les lignes suivantes, une liste de P éléments : cles, les différentes parties des clés.
    • Une ligne par élément de la liste : une liste de N entiers séparés par des espaces.

Sortie

Afficher, sur une première ligne, le nombre de serrures ouvrables simultanément. Sur une deuxième ligne, afficher, séparés par des espaces, le type de chaque serrure qui peut être ouverte, par ordre croissant de leur type.

Contraintes

  • $1 \le N \le 1\,000$
  • $1 \le P \le 10$
  • Il est garanti qu'au moins une serrure peut être ouverte.
  • $-1\,000\,000 \le t \le 1\,000\,000$, $t$ étant le type d'une serrure ou d'une partie de clé.

Contraintes de performance

  • $1 \le P \le 1\,000$

Runtime constraints

Maximum memory usage
100000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
5
2
2 3 5 5 11
5 7 9 11 13
-1 2 2 5 5
Sample output
1
5
Note

Porte d'entrée

La serrure de type 2 ne peut pas être ouverte, car malgré le fait qu'il existe deux parties de clés de type 2, ces deux parties sont de même forme et ne peuvent donc pas être combinées ensemble.

Il est possible de combiner chaque partie de type 5 afin de former une clé pouvant ouvrir une serrure typée 5. C'est en fait la seule serrure qu'il est possible d'ouvrir. Il n'est pas possible d'ouvrir les deux serrures de type 5 simultanément, car il aurait fallu pouvoir former deux clés de type 5.

Sample input
7
3
-1 -1 0 1 1 1 2
-1 -1 0 0 1 1 1
-1 1 1 1 2 2 2
-1 0 1 1 2 2 2
Sample output
3
-1 1 1
Note

Des deux serrures de type -1, il n'est possible d'en ouvrir qu'une, car vous disposez d'au moins une partie de clé de type -1 de chaque forme, mais pas de deux.

Vous ne pouvez pas ouvrir la serrure de type 0, car vous ne disposez pas de partie de clé intermédiaire de type 0.

Vous pouvez ouvrir deux des trois serrures de type 1, car vous disposez d'au moins deux parties de clé de type 1 de chaque forme.

Au total, vous pourrez ouvrir simultanément 3 serrures.

Submit your solution

You have to register or log in to be able to submit your solution.