█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 810

Problema 0xcf - Mirando al horizonte

  • Autor: orendon
  • Fecha: 2020-09-20 02:00:53 UTC (Hace alrededor de 4 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.006 s 1 KBi
#2
Correcto
0.005 s 1 KBi
#3
Correcto
0.006 s 46 KBi
#4
Correcto
0.005 s 1 KBi
#5
Correcto
0.005 s 7 KBi
#6
Tiempo límite excedido
1.043 s 12 KBi
#7
Tiempo límite excedido
0.961 s 6 KBi
#8
Tiempo límite excedido
1.045 s 5 KBi
#9
Tiempo límite excedido
1.038 s 8 KBi
#10
Tiempo límite excedido
1.062 s 8 KBi
Puntos totales: 50 / 100

Código

// 08
// https://codeo.app/problemas/0xcf-mirando-al-horizonte

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
    int data;
    struct Node *next;
};

int searchBigger(int height, Node *node)
{
    while (node != nullptr)
    {
        if (node->data > height)
            return node->data;
        node = node->next;
    }
    return -1;
}

Node *insertAtBeginning(Node *node, int value)
{
    Node *tempNode = new Node;
    tempNode->data = value;
    tempNode->next = nullptr;

    if (node)
        tempNode->next = node;
    return tempNode;
}

void printList(Node *node)
{
    while (node != nullptr)
    {
        cout << node->data << " ";
        node = node->next;
    }
}

// 2: linked list approach
void solveCase2(vector<int> buildings, int n)
{
    Node *head = nullptr, *output = nullptr;
    int biggerB;
    for (int i = n - 1; i >= 0; i--)
    {
        biggerB = searchBigger(buildings[i], head);
        if (biggerB != buildings[i])
            head = insertAtBeginning(head, buildings[i]);

        output = insertAtBeginning(output, biggerB);
    }
    printList(output);
}

// 1: brute force approach
void solveCase1(vector<int> buildings, int n)
{
    int biggerHeight;
    for (int i = 0; i < n; i++)
    {
        biggerHeight = -1;
        for (int j = i + 1; j < n; j++)
        {
            if (buildings[j] > buildings[i])
            {
                biggerHeight = buildings[j];
                break;
            }
        }
        cout << biggerHeight << " ";
    }
}

int main()
{
    int cases, n;
    vector<int> buildings;

    cin >> cases;
    for (int c = 1; c <= cases; c++)
    {
        // read buildings heights
        cin >> n;
        buildings = vector<int>(n);
        for (int i = 0; i < n; i++)
            cin >> buildings[i];

        // check for building hidding the horizon
        cout << "Case #" << c << ": ";
        solveCase2(buildings, n);
        cout << endl;
    }

    return 0;
}