• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Tamy final OIG

VPS Starter Arubacloud
0 głosów
146 wizyt
pytanie zadane 18 grudnia 2022 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Robie zadanie tamy z finalu 5 OIG-a: https://szkopul.edu.pl/problemset/problem/vjNqpia6QTMVAmkfml9VonDX/site/?key=statement

Zadanie wydaje się dośc proste. Robię seta przepełnień i "zamiatam miotłą po czasie" symulując kolejne zdarzenia. Jednak mam gdzieś bląd w implementacji. Ma ktoś pomysł gdzie? Siedzę już 4 godzinę i nigdzie nie mogę znaleźć, a kod wydaje się być przejrzysty.

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Element_seta_po_rozlaniach
{
    long long po_ilu_rozleje;
    long long szerokosc;
    long long numer;
    long long ile_leci_opadow;
    long long wartosc_lewej_tamy;
    long long wartosc_prawej_tamy;
    bool operator < (const Element_seta_po_rozlaniach &element_seta_po_rozlaniach) const
    {
        if (po_ilu_rozleje == element_seta_po_rozlaniach.po_ilu_rozleje)
            return numer < element_seta_po_rozlaniach.numer;
        return po_ilu_rozleje < element_seta_po_rozlaniach.po_ilu_rozleje;
    }
};

struct Element_seta_po_idxach
{
    long long idx;
    long long po_ilu_rozleje;
    bool operator < (const Element_seta_po_idxach &element_seta_po_idxach) const
    {
        return idx < element_seta_po_idxach.idx;
    }
};

long long n = 0, wczytana_liczba = 0;
vector<long long> tamy;
set<Element_seta_po_rozlaniach> rozlania;
set<Element_seta_po_idxach> numery_sektorow;
Element_seta_po_rozlaniach spr;
Element_seta_po_rozlaniach jeden_lewo;
Element_seta_po_rozlaniach jeden_prawo;

void rozszerzaj_oba()
{
    rozlania.erase({spr.po_ilu_rozleje,-1,spr.numer,-1,-1,-1});
    rozlania.erase({jeden_lewo.po_ilu_rozleje,-1,jeden_lewo.numer,-1,-1,-1});
    rozlania.erase({jeden_prawo.po_ilu_rozleje,-1,jeden_prawo.numer,-1,-1,-1});
    numery_sektorow.erase({spr.numer,-1});
    numery_sektorow.erase({jeden_lewo.numer,-1});
    numery_sektorow.erase({jeden_prawo.numer,-1});
    long long szerokosc = jeden_lewo.szerokosc+spr.szerokosc+jeden_prawo.szerokosc;
    long long suma_opadow = jeden_lewo.ile_leci_opadow + spr.ile_leci_opadow + jeden_prawo.ile_leci_opadow;
    long long min_tamy_obok = min(jeden_lewo.wartosc_lewej_tamy,jeden_prawo.wartosc_prawej_tamy);
    long long po_ilu_roz = szerokosc * min_tamy_obok / suma_opadow + 1;
    rozlania.insert({po_ilu_roz,szerokosc,spr.numer,suma_opadow,jeden_lewo.wartosc_lewej_tamy,jeden_prawo.wartosc_prawej_tamy});
    numery_sektorow.insert({spr.numer,po_ilu_roz});
}

void rozszerzaj_lewy()
{
    rozlania.erase({spr.po_ilu_rozleje,-1,spr.numer,-1,-1,-1});
    rozlania.erase({jeden_lewo.po_ilu_rozleje,-1,jeden_lewo.numer,-1,-1,-1});
    numery_sektorow.erase({spr.numer,-1});
    numery_sektorow.erase({jeden_lewo.numer,-1});
    long long szerokosc = spr.szerokosc + jeden_lewo.szerokosc;
    long long suma_opadow = spr.ile_leci_opadow + jeden_lewo.ile_leci_opadow;
    long long min_tamy_obok = min(jeden_lewo.wartosc_lewej_tamy,spr.wartosc_prawej_tamy);
    long long po_ilu_roz = szerokosc * min_tamy_obok / suma_opadow + 1;
    rozlania.insert({po_ilu_roz,szerokosc,spr.numer,suma_opadow,jeden_lewo.wartosc_lewej_tamy,spr.wartosc_prawej_tamy});
    numery_sektorow.insert({spr.numer,po_ilu_roz});
}

void rozszerzaj_prawy()
{
    rozlania.erase({spr.po_ilu_rozleje,-1,spr.numer,-1,-1,-1});
    rozlania.erase({jeden_prawo.po_ilu_rozleje,-1,jeden_prawo.numer,-1,-1,-1});
    numery_sektorow.erase({spr.numer,-1});
    numery_sektorow.erase({jeden_prawo.numer,-1});
    long long szerokosc = jeden_prawo.szerokosc+spr.szerokosc;
    long long suma_opadow = jeden_prawo.ile_leci_opadow + spr.ile_leci_opadow;
    long long min_tamy_obok = min(spr.wartosc_lewej_tamy,jeden_prawo.wartosc_prawej_tamy);
    long long po_ilu_roz = szerokosc * min_tamy_obok / suma_opadow + 1;
    rozlania.insert({po_ilu_roz,szerokosc,spr.numer,suma_opadow,spr.wartosc_lewej_tamy,jeden_prawo.wartosc_prawej_tamy});
    numery_sektorow.insert({spr.numer,po_ilu_roz});
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i <= n; ++i)
    {
        cin >> wczytana_liczba;
        tamy.push_back(wczytana_liczba);
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> wczytana_liczba;
        long long po_ilu_roz = min(tamy[i-1],tamy[i]) / wczytana_liczba + 1;
        rozlania.insert({po_ilu_roz,1,i,wczytana_liczba,tamy[i-1],tamy[i]});
        numery_sektorow.insert({i,po_ilu_roz});
    }

    while(true)
    {
        spr = *rozlania.begin();
        jeden_lewo = {-1,-1,-1,-1,-1,-1};
        jeden_prawo = {-1,-1,-1,-1,-1,-1};
        if (numery_sektorow.begin()->idx != spr.numer)
        {
            auto it_numery = numery_sektorow.find({spr.numer,spr.po_ilu_rozleje});
            --it_numery;
            jeden_lewo = *(rozlania.find({it_numery->po_ilu_rozleje,-1,it_numery->idx,-1,-1,-1}));
        }
        if (numery_sektorow.rbegin()->idx != spr.numer)
        {
            auto it_numery = numery_sektorow.find({spr.numer,spr.po_ilu_rozleje});
            ++it_numery;
            jeden_prawo = *(rozlania.find({it_numery->po_ilu_rozleje,-1,it_numery->idx,-1,-1,-1}));
        }

        if (jeden_lewo.po_ilu_rozleje == -1 && jeden_prawo.po_ilu_rozleje == -1)
        {
            printf("%lld",spr.po_ilu_rozleje);
            return 0;
        }
        else if (jeden_lewo.po_ilu_rozleje == -1)
        {
            if (spr.wartosc_lewej_tamy <= spr.wartosc_prawej_tamy)
            {
                printf("%lld",spr.po_ilu_rozleje);
                return 0;
            }
            else
                rozszerzaj_prawy();
        }
        else if (jeden_prawo.po_ilu_rozleje == -1)
        {
            if (spr.wartosc_prawej_tamy <= spr.wartosc_lewej_tamy)
            {
                printf("%lld",spr.po_ilu_rozleje);
                return 0;
            }
            else
                rozszerzaj_lewy();
        }
        else
        {
            if (spr.wartosc_lewej_tamy == spr.wartosc_prawej_tamy)
                rozszerzaj_oba();
            else if (spr.wartosc_lewej_tamy < spr.wartosc_prawej_tamy)
                rozszerzaj_lewy();
            else
                rozszerzaj_prawy();
        }
    }
    return 0;
}

Dziękuję za pomoc.

komentarz 18 grudnia 2022 przez Whistleroosh Maniak (56,980 p.)
6
6 8 13 2 14 12 9
1 1 3 10 5 1

Przykład dla którego jest błędna odpowiedź. Powinno być 3 program wypisuje 2

komentarz 18 grudnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
A to nie powinno być 2?
komentarz 18 grudnia 2022 przez Whistleroosh Maniak (56,980 p.)
Po drugiej sekundzie woda między tamami o wysokościach 13 i 14 jest dokładnie na wysokości 13 i w 3 sekundzie wyleje sie z lewej strony
komentarz 18 grudnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Bardzo cięzko to wsm zaimplementowac. Napisalem cos takiego:

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Element_seta_po_rozlaniach
{
    long long po_ilu_rozleje;
    long long szerokosc;
    long long numer;
    long long ile_leci_opadow;
    long long wartosc_lewej_tamy;
    long long wartosc_prawej_tamy;
    bool operator < (const Element_seta_po_rozlaniach &element_seta_po_rozlaniach) const
    {
        if (po_ilu_rozleje == element_seta_po_rozlaniach.po_ilu_rozleje)
            return numer < element_seta_po_rozlaniach.numer;
        return po_ilu_rozleje < element_seta_po_rozlaniach.po_ilu_rozleje;
    }
};

struct Element_seta_po_idxach
{
    long long idx;
    long long po_ilu_rozleje;
    bool operator < (const Element_seta_po_idxach &element_seta_po_idxach) const
    {
        return idx < element_seta_po_idxach.idx;
    }
};

long long n = 0, wczytana_liczba = 0;
vector<long long> tamy;
set<Element_seta_po_rozlaniach> rozlania;
set<Element_seta_po_idxach> numery_sektorow;
Element_seta_po_rozlaniach spr;
Element_seta_po_rozlaniach jeden_lewo;
Element_seta_po_rozlaniach jeden_prawo;

void rozszerzaj_oba()
{
    rozlania.erase({spr.po_ilu_rozleje,-1,spr.numer,-1,-1,-1});
    rozlania.erase({jeden_lewo.po_ilu_rozleje,-1,jeden_lewo.numer,-1,-1,-1});
    rozlania.erase({jeden_prawo.po_ilu_rozleje,-1,jeden_prawo.numer,-1,-1,-1});
    numery_sektorow.erase({spr.numer,-1});
    numery_sektorow.erase({jeden_lewo.numer,-1});
    numery_sektorow.erase({jeden_prawo.numer,-1});
    long long szerokosc = jeden_lewo.szerokosc+spr.szerokosc+jeden_prawo.szerokosc;
    long long suma_opadow = jeden_lewo.ile_leci_opadow + spr.ile_leci_opadow + jeden_prawo.ile_leci_opadow;
    long long min_tamy_obok = min(jeden_lewo.wartosc_lewej_tamy,jeden_prawo.wartosc_prawej_tamy);
    long long po_ilu_roz = max(spr.po_ilu_rozleje,szerokosc * min_tamy_obok / suma_opadow + 1);
    rozlania.insert({po_ilu_roz,szerokosc,spr.numer,suma_opadow,jeden_lewo.wartosc_lewej_tamy,jeden_prawo.wartosc_prawej_tamy});
    numery_sektorow.insert({spr.numer,po_ilu_roz});
}

void rozszerzaj_lewy()
{
    rozlania.erase({spr.po_ilu_rozleje,-1,spr.numer,-1,-1,-1});
    rozlania.erase({jeden_lewo.po_ilu_rozleje,-1,jeden_lewo.numer,-1,-1,-1});
    numery_sektorow.erase({spr.numer,-1});
    numery_sektorow.erase({jeden_lewo.numer,-1});
    long long szerokosc = spr.szerokosc + jeden_lewo.szerokosc;
    long long suma_opadow = spr.ile_leci_opadow + jeden_lewo.ile_leci_opadow;
    long long min_tamy_obok = min(jeden_lewo.wartosc_lewej_tamy,spr.wartosc_prawej_tamy);
    long long po_ilu_roz = max(spr.po_ilu_rozleje,szerokosc * min_tamy_obok / suma_opadow + 1);
    rozlania.insert({po_ilu_roz,szerokosc,spr.numer,suma_opadow,jeden_lewo.wartosc_lewej_tamy,spr.wartosc_prawej_tamy});
    numery_sektorow.insert({spr.numer,po_ilu_roz});
}

void rozszerzaj_prawy()
{
    rozlania.erase({spr.po_ilu_rozleje,-1,spr.numer,-1,-1,-1});
    rozlania.erase({jeden_prawo.po_ilu_rozleje,-1,jeden_prawo.numer,-1,-1,-1});
    numery_sektorow.erase({spr.numer,-1});
    numery_sektorow.erase({jeden_prawo.numer,-1});
    long long szerokosc = jeden_prawo.szerokosc+spr.szerokosc;
    long long suma_opadow = jeden_prawo.ile_leci_opadow + spr.ile_leci_opadow;
    long long min_tamy_obok = min(spr.wartosc_lewej_tamy,jeden_prawo.wartosc_prawej_tamy);
    long long po_ilu_roz = max(spr.po_ilu_rozleje,szerokosc * min_tamy_obok / suma_opadow + 1);
    rozlania.insert({po_ilu_roz,szerokosc,spr.numer,suma_opadow,spr.wartosc_lewej_tamy,jeden_prawo.wartosc_prawej_tamy});
    numery_sektorow.insert({spr.numer,po_ilu_roz});
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i <= n; ++i)
    {
        cin >> wczytana_liczba;
        tamy.push_back(wczytana_liczba);
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> wczytana_liczba;
        long long po_ilu_roz = min(tamy[i-1],tamy[i]) / wczytana_liczba + 1;
        rozlania.insert({po_ilu_roz,1,i,wczytana_liczba,tamy[i-1],tamy[i]});
        numery_sektorow.insert({i,po_ilu_roz});
    }

    while(true)
    {
        spr = *rozlania.begin();
        //cout << "Begin: Po ilu rozleje: " << spr.po_ilu_rozleje << " Numer: " << spr.numer << " Szerokosc " << spr.szerokosc << " Ile leci opadow: " << spr.ile_leci_opadow << " Wysokosc lewej tamy: " << spr.wartosc_lewej_tamy << " Wysokosc prawej tamy: " << spr.wartosc_prawej_tamy << endl;
        jeden_lewo = {-1,-1,-1,-1,-1,-1};
        jeden_prawo = {-1,-1,-1,-1,-1,-1};
        if (numery_sektorow.begin()->idx != spr.numer)
        {
            auto it_numery = numery_sektorow.find({spr.numer,spr.po_ilu_rozleje});
            --it_numery;
            jeden_lewo = *(rozlania.find({it_numery->po_ilu_rozleje,-1,it_numery->idx,-1,-1,-1}));
        }
        if (numery_sektorow.rbegin()->idx != spr.numer)
        {
            auto it_numery = numery_sektorow.find({spr.numer,spr.po_ilu_rozleje});
            ++it_numery;
            jeden_prawo = *(rozlania.find({it_numery->po_ilu_rozleje,-1,it_numery->idx,-1,-1,-1}));
        }

        if (jeden_lewo.po_ilu_rozleje == -1 && jeden_prawo.po_ilu_rozleje == -1)
        {
            printf("%lld",spr.po_ilu_rozleje);
            return 0;
        }
        else if (jeden_lewo.po_ilu_rozleje == -1)
        {
            if (spr.wartosc_lewej_tamy <= spr.wartosc_prawej_tamy)
            {
                printf("%lld",spr.po_ilu_rozleje);
                return 0;
            }
            else
                rozszerzaj_prawy();
        }
        else if (jeden_prawo.po_ilu_rozleje == -1)
        {
            if (spr.wartosc_prawej_tamy <= spr.wartosc_lewej_tamy)
            {
                printf("%lld",spr.po_ilu_rozleje);
                return 0;
            }
            else
                rozszerzaj_lewy();
        }
        else
        {
            if (spr.wartosc_lewej_tamy == spr.wartosc_prawej_tamy)
                rozszerzaj_oba();
            else if (spr.wartosc_lewej_tamy < spr.wartosc_prawej_tamy)
                rozszerzaj_lewy();
            else
                rozszerzaj_prawy();
        }
    }
    return 0;
}

W tym cas-ie sie juz nie wywala, ale ogolnie jest zle 0pkt. Ciezko mi znalezc jakis test, gdzie sie wywala. A co ciekawe przechodzi wszystkie przykładowe testy. tylko w 1 sie czas wywala.(w sensie przykladowym)

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
0 odpowiedzi 466 wizyt
pytanie zadane 16 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
2 odpowiedzi 407 wizyt
pytanie zadane 28 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 172 wizyt
pytanie zadane 24 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,775 zapytań

141,703 odpowiedzi

320,556 komentarzy

62,109 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...