Mam takie zadanie z III etapu V OIG:
Tamy
Limit pamięci: 64 MB
W Bajtocji zbudowano wielki zbiornik wodny. Podzielono go na pewną liczbę jednakowej długości sektorów. Pomiędzy każdymi dwoma sąsiednimi sektorami znalazła się tama o pewnej wysokości. Tamy zbudowano także przed pierwszym oraz za ostatnim sektorem.
Obecnie poziom wody w całym zbiorniku jest taki sam. Ponieważ jednak zaczął padać ulewny deszcz, poziom wody zaczął szybko wzrastać. Król Bajtocji chce wiedzieć, ile czasu upłynie, zanim woda przeleje się przez pierwszą lub przez ostatnią tamę, wskutek czego pewnikiem dojdzie do zalania Bajtocji. Obliczenie tego utrudnia fakt, że nad każdym z sektorów deszcz może padać z różną intensywnością.
Pomóż królowi obliczyć czas, jaki pozostał do wylania się wody poza zbiornik. Jeżeli poziom wody jest równy dokładnie wysokości tamy, woda jeszcze się nie wylewa. Gdy część zbiornika już zalana wodą jest ograniczona z obu stron tamami tej samej wysokości, woda przelewa się z niej w obie strony równie szybko.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą 
(
), oznaczającą liczbę sektorów, na jakie podzielony jest zbiornik.
Drugi wiersz zawiera ciąg 
liczb całkowitych 
(
) pooddzielanych pojedynczymi odstępami, oznaczających wysokości (ponad początkowy poziom wody) kolejnych tam.
Trzeci wiersz zawiera ciąg 
liczb całkowitych 
(
) pooddzielanych pojedynczymi odstępami, oznaczających, o ile poziomów woda podnosi się w 
-tym sektorze w ciągu jednej sekundy.
Możesz założyć, że w testach wartych przynajmniej 
punktów wysokości tam są parami różne. Ponadto, w części tych testów, wartych co najmniej 
punktów, zachodzi warunek 
.
Wyjście
Pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, będącą najmniejszą liczbą całkowitą nie mniejszą niż liczba sekund, po których woda wyleje się ze zbiornika.
Przykład
Dla danych wejściowych:
4
3 5 2 6 4
1 3 3 1
poprawną odpowiedzią jest:
2
Generalnie to przeczytalem pomysl wzorcowy na to zadanie, ale gdzies w implementacji mam blad i zadanie przechodzi tylko na 18 punktow. Czy bylby ktos w stanie mi pomoc go znalezc? Oto moj kod:
#include<bits/stdc++.h>
using namespace std;
vector<int> tamy;
vector<double> przyrost;
vector<pair<double, double>> dane;
vector<double> czas;
struct Node{
double czas;
double indx;
double ile_odjete;
Node(double p_czas, double p_indx, double p_ile_odjete): czas(p_czas), indx(p_indx), ile_odjete(p_ile_odjete) {}
};
class Kopiec{
public:
double czas_all=0;
vector<Node> tablica = vector<Node>(1, Node(0, 0, 0));
void wstaw(Node e){
tablica.push_back(e);
int w = tablica.size()-1;
while(w > 1 && tablica[w].czas < tablica[w/2].czas){
swap(tablica[w], tablica[w/2]);
w/=2;
}
}
void przywroc(int i){
int lewy = 2*i;
int prawy = 2*i+1;
int maks = i;
if(lewy < tablica.size() && tablica[lewy].czas<tablica[maks].czas)
maks = lewy;
if(prawy < tablica.size() && tablica[prawy].czas<tablica[maks].czas)
maks = prawy;
if(maks > i){
swap(tablica[i], tablica[maks]);
przywroc(maks);
}
}
void buduj(){
for(int i = tablica.size()/2; i >= 1; i--)
przywroc(i);
}
void usun(){
tablica[1]=tablica[tablica.size()-1];
tablica.pop_back();
przywroc(1);
}
void przelej_lewo(bool czyObieStrony){
int it=tablica[1].indx-1;
while(it >= 0 && przyrost[it]==-1)
it--;
double v = przyrost[it]*czas_all;
przyrost[it] += dane[tablica[1].indx].first/dane[it].second;
dane[it].first+=dane[tablica[1].indx].first;
if(czyObieStrony){
przyrost[it]/=2;
dane[it].first/=2;
}
przyrost[tablica[1].indx] = -1;
usun();
uaktualnij_czas();
czas[it]=(tamy[it]-v)/przyrost[it];
wstaw(Node((tamy[it]-v)/przyrost[it], it, czas_all));
}
void przelej_prawo(bool czyObieStrony){
int it=tablica[1].indx+1;
while(it < przyrost.size() && przyrost[it]==-1)
it++;
double v = przyrost[it]*czas_all;
przyrost[it] += dane[tablica[1].indx].first/dane[it].second;
dane[it].first+=dane[tablica[1].indx].first;
if(czyObieStrony){
przyrost[it]/=2;
dane[it].first/=2;
}
przyrost[tablica[1].indx] = -1;
usun();
uaktualnij_czas();
czas[it]=(tamy[it+1]-v)/przyrost[it];
wstaw(Node((tamy[it+1]-v)/przyrost[it], it, czas_all));
}
void uaktualnij_czas(){
if(tablica.size() >= 4){
for(int i=1; i<4; i++){
if(tablica[i].czas==czas[tablica[i].indx]){
tablica[i].czas = tablica[i].czas-(czas_all-tablica[i].ile_odjete);
tablica[i].ile_odjete=czas_all;
czas[tablica[i].indx] = tablica[i].czas;
}
}
}
else{
for(int i=1; i<tablica.size(); i++){
if(tablica[i].czas==czas[tablica[i].indx]){
tablica[i].czas = tablica[i].czas-(czas_all-tablica[i].ile_odjete);
tablica[i].ile_odjete=czas_all;
czas[tablica[i].indx] = tablica[i].czas;
}
}
}
przywroc(1);
}
bool ruch(){
if(tablica.size()==1)
return true;
if(tablica[1].czas!=czas[tablica[1].indx]){
tablica[1]=tablica[tablica.size()-1];
tablica.pop_back();
przywroc(1);
return false;
}
czas_all += tablica[1].czas;
if(tablica[1].czas == tamy[0]/przyrost[0] || tablica[1].czas == tamy[tamy.size()-1]/przyrost[przyrost.size()-1])
return true;
if(tablica[1].indx==0 || tablica[1].indx==przyrost.size()-1)
return true;
if(tamy[tablica[1].indx] < tamy[tablica[1].indx+1])
przelej_lewo(false);
else if(tamy[tablica[1].indx] > tamy[tablica[1].indx+1])
przelej_prawo(false);
else{
przelej_lewo(true);
przelej_prawo(true);
}
return false;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
int tamy_wczytane[n+1];
int przyrost_wczytane[n];
for(int i=0; i<n+1; i++)
cin >> tamy_wczytane[i];
for(int i=0; i<n; i++)
cin >> przyrost_wczytane[i];
pair<int, int> maks = make_pair(0, 0);
for(int i=0; i<n+1; i++){
if(maks.first < tamy_wczytane[i])
maks = make_pair(tamy_wczytane[i], i);
}
double suma=0;
double it=0;
tamy.push_back(tamy_wczytane[0]);
for(int i=1; i<=maks.second; i++){
if(tamy_wczytane[i] >= tamy[tamy.size()-1]){
tamy.push_back(tamy_wczytane[i]);
it++;
suma+=przyrost_wczytane[i-1];
dane.push_back(make_pair(suma, it));
przyrost.push_back(suma/it);
it=0;
suma=0;
}
else{
suma+=przyrost_wczytane[i-1];
it++;
}
}
it=0;
suma=0;
stack<int> stos_tamy;
stack<double> stos_przyrost;
stack<pair<int, int>> stos_dane;
if(n!=maks.second)
stos_tamy.push(tamy_wczytane[n]);
for(int i=n-1; i>=maks.second; i--){
int top = stos_tamy.top();
if(tamy_wczytane[i] >= top){
suma+=przyrost_wczytane[i];
it++;
if(i!=maks.second)stos_tamy.push(tamy_wczytane[i]);
stos_przyrost.push(suma/it);
stos_dane.push(make_pair(suma, it));
it=0;
suma=0;
}
else{
suma+=przyrost_wczytane[i];
it++;
}
}
if(it!=0){
stos_przyrost.push(suma/it);
stos_dane.push(make_pair(suma, it));
}
while(!stos_tamy.empty()){
int top = stos_tamy.top();
tamy.push_back(top);
stos_tamy.pop();
}
while(!stos_przyrost.empty()){
double top = stos_przyrost.top();
przyrost.push_back(top);
stos_przyrost.pop();
}
while(!stos_dane.empty()){
pair<int, int> top = stos_dane.top();
dane.push_back(top);
stos_dane.pop();
}
Kopiec* kopiec_lewy = new Kopiec;
Kopiec* kopiec_prawy = new Kopiec;
bool mode = true;
for(int i=0; i<przyrost.size(); i++){
if(tamy[i] == maks.first)
mode=false;
if(mode){
int h = min(tamy[i], tamy[i+1]);
kopiec_lewy->tablica.push_back(Node(h/przyrost[i], i, 0));
czas.push_back(h/przyrost[i]);
}
else{
int h = min(tamy[i], tamy[i+1]);
kopiec_prawy->tablica.push_back(Node(h/przyrost[i], i, 0));
czas.push_back(h/przyrost[i]);
}
}
kopiec_lewy->buduj();
kopiec_prawy->buduj();
while(!kopiec_lewy->ruch());
while(!kopiec_prawy->ruch());
if(kopiec_lewy->czas_all==0){
if(kopiec_prawy->czas_all!=int(kopiec_prawy->czas_all))
kopiec_prawy->czas_all=ceil(kopiec_prawy->czas_all);
else
kopiec_prawy->czas_all++;
cout << kopiec_prawy->czas_all<< endl;
delete kopiec_lewy;
delete kopiec_prawy;
return 0;
}
else if(kopiec_prawy->czas_all==0){
if(kopiec_lewy->czas_all!=int(kopiec_lewy->czas_all))
kopiec_lewy->czas_all=ceil(kopiec_lewy->czas_all);
else
kopiec_lewy->czas_all++;
cout << kopiec_lewy->czas_all << endl;
delete kopiec_lewy;
delete kopiec_prawy;
return 0;
}
if(kopiec_lewy->czas_all!=int(kopiec_lewy->czas_all))
kopiec_lewy->czas_all=ceil(kopiec_lewy->czas_all);
else
kopiec_lewy->czas_all++;
if(kopiec_prawy->czas_all!=int(kopiec_prawy->czas_all))
kopiec_prawy->czas_all=ceil(kopiec_prawy->czas_all);
else
kopiec_prawy->czas_all++;
cout << min(kopiec_lewy->czas_all, kopiec_prawy->czas_all) << endl;
delete kopiec_lewy;
delete kopiec_prawy;
return 0;
}
Z gory dziekuje za wszystkie odpowiedzi
