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.
