Un ordinateur spécialisé, conçu pour manipuler des ensembles, opère sur une pile initialement vide. Il supporte les opérations suivantes :

• PUSH : Empile un ensemble vide {}.
• DUP : Duplique l'élément au sommet de la pile et l'empile.
• UNION : Dépile deux ensembles, calcule leur union et empile le résultat.
• INTERSECT : Dépile deux ensembles, calcule leur intersection et empile le résultat.
• ADD : Dépile deux ensembles. L'ensemble dépilé en premier est ajouté comme élément au second ensemble dépilé. Le nouvel ensemble est ensuite empilé.

Après chaque opération, la taille (nombre d'éléments) de l'ensemble au sommet de la pile est affichée.

Exemple illustratif :
Soient les ensembles A = { {}, {{}} } et B = { {}, {{{}}} }.

• Une opération UNION produirait { {}, {{}}, {{{}}} }, affichage : 3
• Une opération INTERSECT produirait { {} }, affichage : 1
• Une opération ADD produirait { {}, {{{}}}, { {}, {{}} } }, affichage : 3

Exemple d'entrée/sortie :

6
PUSH
PUSH
UNION
PUSH
PUSH
ADD

Sortie correspondante :

0
0
0
0
0
1

Approche et Structures de Données

Le défi principal réside dans la gestion des ensembles imbriqués (par exemple, set<set<...>>) en C++, ce qui n'est pas direcetment supporté par std::set pour des raisons de comparaison d'éléments. Pour contourner cette limitation, nous attribuons un identifiant entier unique (ID) à chaque ensemble distinct. Ainsi, un ensemble contenant d'autres ensembles est représenté comme un std::set<int>, où chaque entier est l'ID d'un sous-ensemble.

Pour implémenter ce système, nous utiliserons les conteneurs C++ suivants :

• EnsembleID (alias pour std::set<int>) : Représente un ensemble. Ses éléments sont les IDs des ensembles qu'il contient.
• stockageEnsemblesUniques (de type std::vector<EnsembleID>) : Agit comme un référentiel global de tous les objets EnsembleID uniques créés. L'indice de chaque ensmeble dans ce vecteur est son ID unique.
• mappingEnsembleVersID (de type std::map<EnsembleID, int>) : Mappe chaque objet EnsembleID à son ID entier unique correspondant. Ceci est essentiel pour rechercher rapidement si un ensemble a déjà un ID attribué, évitant ainsi les duplications et garantissant la cohérence.
• pileOperations (de type std::stack<int>) : La pile de la machine virtuelle. Elle stocke les IDs des ensembles, plutôt que les ensembles eux-mêmes.

Définitions de types et structures globales

#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <stack>
#include <string>
#include <algorithm> // Pour std::set_union, std::set_intersection
#include <iterator>  // Pour std::inserter

// Définit un ensemble d'entiers, où chaque entier est l'ID d'un autre ensemble.
using EnsembleID = std::set<int>;

// Stocke tous les ensembles uniques créés, indexés par leur ID.
std::vector<EnsembleID> stockageEnsemblesUniques;
// Mappe chaque EnsembleID à son ID unique.
std::map<EnsembleID, int> mappingEnsembleVersID;
// La pile de la machine, contenant les IDs des ensembles.
std::stack<int> pileOperations;

// Prototype de la fonction pour obtenir ou créer l'ID d'un ensemble.
int obtenirIDEnsemble(const EnsembleID& ensemble);

Implémentation des Opérations

Fonction utilitaire : obtenirIDEnsemble

Cette fonction est cruciale pour le système d'identification des ensembles. Elle prend un EnsembleID en argument. Si cet ensemble a déjà un ID attribué (c'est-à-dire qu'il est déjà dans mappingEnsembleVersID), elle retourne cet ID. Sinon, elle lui attribue un nouvel ID basé sur la taille actuelle de stockageEnsemblesUniques, le stocke dans stockageEnsemblesUniques et met à jour mappingEnsembleVersID avant de retourner le nouvel ID.

int obtenirIDEnsemble(const EnsembleID& ensemble) {
    // Vérifie si l'ensemble existe déjà dans le mapping.
    auto it = mappingEnsembleVersID.find(ensemble);
    if (it != mappingEnsembleVersID.end()) {
        return it->second; // Retourne l'ID existant.
    }

    // L'ensemble est nouveau : lui attribuer un nouvel ID.
    int nouvelID = stockageEnsemblesUniques.size();
    stockageEnsemblesUniques.push_back(ensemble); // Stocke l'ensemble.
    mappingEnsembleVersID[ensemble] = nouvelID; // Mappe l'ensemble à son nouvel ID.
    return nouvelID;
}

Logique principale et exécution des commandes

Le programme lit le nombre d'opérations, puis exécute une boucle pour traiter chaque commande. Les optimisations d'entrée/sortie std::ios_base::sync_with_stdio(false) et std::cin.tie(NULL) sont utilisées pour accélérer l'exécution, courantes en programmation compétitive.

int main() {
    std::ios_base::sync_with_stdio(false); // Optimisation I/O
    std::cin.tie(NULL);                   // Optimisation I/O

    int nombreOperations;
    std::cin >> nombreOperations;

    std::string commandeActuelle;
    for (int i = 0; i < nombreOperations; ++i) {
        std::cin >> commandeActuelle;

        if (commandeActuelle[0] == 'P') { // PUSH
            pileOperations.push(obtenirIDEnsemble(EnsembleID())); // Empile l'ID d'un ensemble vide
        } else if (commandeActuelle[0] == 'D') { // DUP
            pileOperations.push(pileOperations.top()); // Duplique l'ID au sommet de la pile
        } else { // UNION, INTERSECT, ADD
            // Dépile les IDs des deux opérandes
            // idOp1 est le premier dépilé, idOp2 est le second (qui était juste en-dessous)
            int idOp1 = pileOperations.top(); pileOperations.pop();
            int idOp2 = pileOperations.top(); pileOperations.pop();

            // Récupère les ensembles réels associés à ces IDs
            const EnsembleID& ensemble1 = stockageEnsemblesUniques[idOp1];
            const EnsembleID& ensemble2 = stockageEnsemblesUniques[idOp2];

            EnsembleID resultatOperation; // Pour stocker le nouvel ensemble résultant

            if (commandeActuelle[0] == 'U') { // UNION
                std::set_union(ensemble1.begin(), ensemble1.end(),
                               ensemble2.begin(), ensemble2.end(),
                               std::inserter(resultatOperation, resultatOperation.begin()));
            } else if (commandeActuelle[0] == 'I') { // INTERSECT
                std::set_intersection(ensemble1.begin(), ensemble1.end(),
                                      ensemble2.begin(), ensemble2.end(),
                                      std::inserter(resultatOperation, resultatOperation.begin()));
            } else if (commandeActuelle[0] == 'A') { // ADD
                // L'opération ADD ajoute l'ensemble désigné par idOp1
                // comme un élément dans une copie de l'ensemble désigné par idOp2.
                // Donc, on commence par copier ensemble2, puis on y insère idOp1.
                resultatOperation = ensemble2;
                resultatOperation.insert(idOp1);
            }
            // Empile l'ID du nouvel ensemble résultant
            pileOperations.push(obtenirIDEnsemble(resultatOperation));
        }
        // Affiche la taille de l'ensemble au sommet de la pile après chaque opération
        // On récupère l'ID du sommet de la pile, puis l'ensemble réel via stockageEnsemblesUniques,
        // et enfin sa taille.
        std::cout << stockageEnsemblesUniques[pileOperations.top()].size() << std::endl;
    }

    return 0;
}

// Définition complète de la fonction utilitaire obtenirIDEnsemble
// (placée ici pour la conformité avec le standard C++ si non déclarée ailleurs comme inline)
int obtenirIDEnsemble(const EnsembleID& ensemble) {
    auto recherche = mappingEnsembleVersID.find(ensemble);
    if (recherche != mappingEnsembleVersID.end()) {
        return recherche->second; // L'ensemble existe déjà, retourne son ID.
    }

    // C'est un nouvel ensemble. Lui attribuer un ID et le stocker.
    int nouvelIdentifiant = stockageEnsemblesUniques.size();
    stockageEnsemblesUniques.push_back(ensemble);
    mappingEnsembleVersID[ensemble] = nouvelIdentifiant;
    return nouvelIdentifiant;
}