1340 - Eu Posso Adivinhar a Estrutura de Dados!

Um dos meus problemas favoritos da plataforma!

Descrição

https://www.beecrowd.com.br/judge/pt/problems/view/1340www.beecrowd.com.br

Solução

Esse problema é bem legal porque você pode implementar as três estruturas de dados e ir simulando cada uma das operações em cada estrutura de cada vez. Se a operação 2 daria erro (importante prever antes de fazer a operação) ou não obtiver o elemento esperado pela entrada, então simplesmente paramos de interagir com aquela estrutura de dados específica.

Mesmo que tenhamos descartado todas as estruturas de dados da resposta, ainda precisamos ler a entrada até o final para não confundir casos de teste diferentes.

O heap implementado na biblioteca em Python ordena do menor para o maior elemento. Logo, tivemos que colocar os elementos com valor negativo para que a ordem fosse a mesma pedida no enunciado.

C++17

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int main()
{
    bool p, f, fp;
    queue<int> fila;
    stack<int> pilha;
    int n, operacao, numero;
    priority_queue<int> filaPrioridade;

    while (cin >> n)
    {
        while (!pilha.empty())
            pilha.pop();
        while (!fila.empty())
            fila.pop();
        while (!filaPrioridade.empty())
            filaPrioridade.pop();

        p = true, f = true, fp = true;
        for (int i = 0; i < n; ++i)
        {
            cin >> operacao >> numero;

            if (operacao == 1)
            {
                if (p)
                    pilha.push(numero);
                if (f)
                    fila.push(numero);
                if (fp)
                    filaPrioridade.push(numero);
            }
            else
            {
                if (p)
                {
                    if (pilha.empty() || pilha.top() != numero)
                        p = false;
                    else
                        pilha.pop();
                }

                if (f)
                {
                    if (fila.empty() || fila.front() != numero)
                        f = false;
                    else
                        fila.pop();
                }

                if (fp)
                {
                    if (filaPrioridade.empty() || filaPrioridade.top() != numero)
                        fp = false;
                    else
                        filaPrioridade.pop();
                }
            }
        }

        if (p && !f && !fp)
            cout << "stack" << endl;
        else if (!p && f && !fp)
            cout << "queue" << endl;
        else if (!p && !f && fp)
            cout << "priority queue" << endl;
        else if (!p && !f && !fp)
            cout << "impossible" << endl;
        else
            cout << "not sure" << endl;
    }

    return 0;
}

Python 3.9