Statuettes – Qualification 2019

Level 5

Énoncé

C'est maintenant la fin des vacances pour Haruhi et Joseph, Haruhi est à l'Île de Pâques et cherche un cadeau pour son groupe d'amis. Elle découvre une guirlande composée de statuettes de l'île, de différentes tailles. Son groupe d'amis a une photo emblématique et pour y faire un clin d'œil elle aimerait avoir un bout de cette guirlande où chacune des statues représente un des amis du groupe. Les amis sont reconnaîssables par leurs tailles relatives respectives.

Entrée

L'entrée comprendra :

  • Deux entiers, $n$ le nombre d'amis sur la photo, et $m$ la taille totale de la guirlande (le nombre de statuettes sur la guirlande).
  • Sur la ligne suivante, $n$ entiers $1 \leq p_i \leq n$ donnent la position du ième ami le plus petit. Ces tailles forment une permutation de ${1, \dots, n}$.
  • Si $p_i = k$ alors l'ami en position $k$ est le $i$-ème plus petit des $n$ amis sur la photo.
  • Sur la ligne suivante $m$ entiers $h_j$, la taille de la statuette en position $j$.

Sortie

Donner toutes les positions où Haruhi peut trouver une apparition des tailles relatives de ses amis. Sur la première ligne le nombre d'apparitions $a$, sur la suivante $a$ entiers, les positions de début des apparitions.

Contraintes

  • $ 1 \le n \le 1 000 000$ et $ 1 \le m \le 200 000 $
  • $ 1 \le p_i \le n $ pour $1 \leq i \leq n$
  • $ 1 \le h_j \le 10^9 $ pour $1 \leq j \leq m$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9
Sample output
2
2 6
Note

Premièrement, on peut passer de l'entrée 2 1 5 3 4, qui représente la position des amis du plus petit au plus grand, aux tailles les plus simples qui puissent correspondre : 2 1 4 5 3. Puis on peut comparer les formes :

Un aperçu du premier exemple

Il y a deux sections de la guirlande que l'on pourrait couper pour avoir une représentation de la photo, en position 2 et en position 6.

  • dans la première apparition, les amis respectivement de tailles 6 3 8 12 7.
  • dans la deuxième apparition, les amis respectivement de tailles 7 1 10 11 9.

Dans les deux cas on a bien l'ami le plus petit en deuxième position en partant de la droite, le deuxième plus petit en première position, le troisième plus petit en cinquième position, et ainsi de suite.

Sample input
6 30
5 4 2 3 1 6
4 17 21 8 5 27 22 23 19 20 12 1 29 3 28 14 6 26 30 24 7 2 15 13 16 25 9 11 10 18
Sample output
1
8
Note

Pareil que dans le premier exemple, on peut passer de 5 4 2 3 1 6 à 5 3 4 2 1 6 et puis essayer de retrouver la forme :

Un aperçu du second exemple

On ne trouve qu'une position (en 8) :

  • les amis représentés sur la guirlande seraient respectivement de tailles 23 19 20 12 1 29.

On a $ 1 < 12 < 19 < 20 < 23 < 29 $ donc on a bien que la premier ami en partant de la droite sur la photo est le 5ème plus petit.

Submit your solution

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