Prévision rotationnelle 2 – Épreuve régionale 2023

Niveau 4

Énoncé

Le présent du mathématicien tout juste récupéré, Cyril et Raphaël tentent de l'analyser pour comprendre son utilité. Pendant ce temps, Valérian tente d'actionner un levier sur deux pour toujours mieux comprendre l'encodage, et lance la machine.

Une fois arrivé, pendant que Cyril et Raphaël manipulent la machine du mathématicien, les quatre autres jeunes partent explorer les alentours pour déterminer en quelle année ils sont arrivés. Hélas, ils posèrent les pieds dans le château d'un seigneur peu recommandable, qui, étonné de leurs vêtements peu commodes, les fit immédiatement prisonnier ! Afin de se libérer, les quatre jeunes doivent suivre les ordres du garde du seigneur pour gagner sa confiance et s'échapper au plus vite.

Voici les instructions que leur a donné le garde du seigneur :

Nobles gens ! Épaulez-moi, vous ferez mon bonheur.
Je dois cultiver les $N$ lopins de mon seigneur,
Mais je suis perdu par l'assolement pluriennal,
Qu'il a imaginé, lassé de l'assolement biennal et triennal
Auquel se consacrait autrefois son vassal.

  • À la parcelle $1$ est cultivée la graine $1$,
  • Sur le lopin $2$ s'accroîssent les germes $2$,
  • [Longue énumération de légumineuses et céréales],
  • Dans le champ $N$, j'avive la semence $N$.

Mon seigneur m'a donné une planification idéale
$G_1, G_2, ..., G_N$ qui sont parmi les symboles $1, ..., N$,
et aucun des nombres n'est à un autre égal.

Chaque année, mon seigneur choisit $X$ un quorum,
Par lequel il m'appartient d'avancer les cultures,
Et $X$ fois j'observe ce décorum :

  • La graine à la parcelle $1$ est déplacée dans le champ $G_1$
  • [Longue énumération de mutations germinales]
  • Les germes sur l'étendue $N-1$ sont avancées à l'herbage $G_{N-1}$
  • Et bien sûr, avant le "Nunc est bibendum",
    La semence sur le lopin $N$ est bougée dans l'enclos $G_N$.

Je souhaite vous faire $R$ requêtes $(T, X)$.

  • Pour $T = 1$, vous me donnerez le grain,
    Qui pousse sur celui que je nomme $X$ parmi les lopins.
  • Celles de type $T = 2$ sont celles de mon suzerain,
    Vous planterez les graines suivant la planification expliquée si bien.

Si vous y parvenez, vous obtiendrez votre libération du châtelain.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : $N$, le nombre de parcelles.
  • Sur la ligne suivante, un entier : $R$, le nombre de requêtes.
  • Sur la ligne suivante, une liste de $N$ entiers séparés par des espaces : $G$, la planification idéale donnée par le seigneur.
  • Sur les lignes suivantes, une liste de $R$ éléments : requetes, la liste des requêtes.
    • Une ligne par élément de la liste : séparés par des espaces, un entier $T$ (le type de la requête), et un entier $X$ (l'argument de la requête).

Sortie

Afficher, pour chaque requête de culture ($T = 1$), la semence qui est actuellement sur la parcelle $X$.

Contraintes

  • $1 \le N \le 100$
  • $1 \le R \le 100$
  • $1 \le T \le 2$
  • $1 \le X \le N$

Contraintes de performance

  • $1 \le N \le 100\,000$
  • $1 \le R \le 100\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
7
4
3 5 1 2 4 7 6
1 2
1 3
2 1
1 7
Exemple de sortie
2
3
6
Commentaire

Il y a 7 parcelles, et 4 requêtes.

Au début, les espèces cultivées sont : $[1, 2, 3, 4, 5, 6, 7]$

  • La première requête demande quelle espèce est plantée dans le 2$^e$ champ : c'est l'espèce $2$.
  • La deuxième requête demande quelle espèce est plantée dans le 3$^e$ champ : c'est l'espèce $3$.
  • La troisième requête demande d'appliquer 1 fois le processus. La graine de la parcelle $1$ sera plantée à la parcelle $3$, celle de la parcelle $2$ à la parcelle $4$, etc.
    À la fin du processus, les espèces cultivées dans les champs sont donc : $[3, 4, 1, 5, 2, 7, 6]$.

exemple

  • La quatrième requête demande quelle espèce est plantée dans le 7$^e$ champ : c'est l'espèce $6$.
Exemple d'entrée
5
6
2 4 3 5 1
2 2
1 1
1 2
1 3
1 4
1 5
Exemple de sortie
4
5
3
1
2
Commentaire

Voici les parcelles initiales : $[1, 2, 3, 4, 5]$.

La première requête applique deux fois le processus :

  • Après une fois : $[5, 1, 3, 2, 4]$.
  • Après deux fois : $[4, 5, 3, 1, 2]$.

Le reste des requêtes affichent toutes les parcelles.

Exemple d'entrée
10
10
6 5 3 4 9 8 7 10 2 1
1 10
2 4
2 10
1 4
2 1
1 3
2 6
2 2
1 1
1 4
Exemple de sortie
10
4
3
6
4