Dzień dobry, potrzebuję Państwa pomocy z jednym zadaniem. Napisałem algorytm, przetestowałem wzdłuż i wszerz, za każdym razem uzyskując poprawną odpowiedź, jednak w systemie sprawdzającym nie zalicza mi żadnych testów. Zadanie polega na pobraniu od użytkownika x liczb z zakresu od 1 do maks. unsigned int. Na tych liczbach wykonywana jest funkcja Collatza, tj. dla liczby n f(n)=3*n + 1 gdy n jest nieparzyste i f(n)=n/2 gdy n jest parzyste. Mamy również dwa rodzaje komend- L i S. L wykonuje funkcje Collatza dla największej liczby z zestawu a S dla najmniejszej. Po wpisaniu zestawu liczb piszemy ilość wszystkich komend. Przed literą piszemy ile komend danego rodzaju ma się wykonać. Ponadto, jeżeli najmniejszą liczbą jest 1 to wybieramy drugą najmniejszą liczbę. Jeśli liczba przekroczy zakres unsigned int to oznaczamy ją. Po wykonaniu wszystkich komend wypisujemy wszystkie liczby z zestawu- jeżeli liczba została oznaczona to na jej miejsce wypisujemy literkę 'm'. Przykładowy input:
4
1 3 3 2000000001
2
2 L
1 S
Gdzie 1 linijka to ilość liczb w zestawie, druga to te liczby, trzecia to ilość wszystkich komend, dwie ostatnie to jakie to są komendy. Przykładowo 2 L oznacza dwa wykonania funkcji dla największej wartości.
Output:
1 10 10 m
Jako struktury do przechowywania liczb użyłem dwóch kopców- minimalnego i maksymalnego. Mój algorytm:
#include <iostream>
#include <climits>
using namespace std;
struct Node{
long long int *data;
int eq_index;
};
int GetLeftChild(int &parent){
return 2*parent+1;
}
int GetRightChild(int &parent){
return 2*parent +2;
}
int GetParent(int &child){
if (child % 2 == 0)
return (child /2 ) -1;
else
return child/2;
}
void DoNode(int index, long long int *data, Node* Max, Node *Min){
Max[index].data=data;
Min[index].data=data;
Max[index].eq_index=index;
Min[index].eq_index=index;
}
void RepUpMax(Node *MAX, Node *MIN, int in){
int P=GetParent(in);
if(P>=0 && (*MAX[P].data<*MAX[in].data || (*MAX[P].data==*MAX[in].data && MAX[P].data>MAX[in].data))){
swap(MIN[MAX[P].eq_index].eq_index,MIN[MAX[in].eq_index].eq_index);
swap(MAX[P].data,MAX[in].data);
swap(MAX[P].eq_index,MAX[in].eq_index);
RepUpMax(MAX,MIN,P);
}
}
void RepUpMin(Node *MAX, Node *MIN, int in){
int P=GetParent(in);
if(*MIN[in].data!=1){
if(P>=0 && (*MIN[P].data>*MIN[in].data || (*MIN[P].data==*MIN[in].data && MIN[P].data>MIN[in].data))){
swap(MAX[MIN[P].eq_index].eq_index,MAX[MIN[in].eq_index].eq_index);
swap(MIN[P].data,MIN[in].data);
swap(MIN[P].eq_index,MIN[in].eq_index);
RepUpMin(MAX,MIN,P);
}
}
}
Node* RepDownMax(Node *MAX, Node *MIN, int in, int size){
int B=in;
int L=GetLeftChild(in);
int R=GetRightChild(in);
if(L<size && (*MAX[B].data<*MAX[L].data || (*MAX[B].data==*MAX[L].data && MAX[B].data>MAX[L].data)))
B=L;
if(R<size && (*MAX[B].data<*MAX[R].data || (*MAX[B].data==*MAX[R].data && MAX[B].data>MAX[R].data)))
B=R;
if(B!=in){
swap(MIN[MAX[B].eq_index].eq_index,MIN[MAX[in].eq_index].eq_index);
swap(MAX[B].data,MAX[in].data);
swap(MAX[B].eq_index,MAX[in].eq_index);
return RepDownMax(MAX,MIN,B,size);
}
return MAX;
}
Node* RepDownMin(Node *MAX, Node *MIN, int in, int size){
int S=in;
int L=GetLeftChild(in);
int R=GetRightChild(in);
if(L<size && (*MIN[S].data>*MIN[L].data || (*MIN[S].data==*MIN[L].data && MIN[S].data>MIN[L].data)))
S=L;
if(R<size && (*MIN[S].data>*MIN[R].data || (*MIN[S].data==*MIN[R].data && MIN[S].data>MIN[R].data)))
S=R;
if(S!=in){
swap(MAX[MIN[S].eq_index].eq_index,MAX[MIN[in].eq_index].eq_index);
swap(MIN[S].data,MIN[in].data);
swap(MIN[S].eq_index,MIN[in].eq_index);
return RepDownMax(MAX,MIN,S,size);
}
return MIN;
}
void RemoveMax(Node*MAX, Node*MIN, int &size, int index){
swap(MIN[MAX[index].eq_index].eq_index,MIN[MAX[size-1].eq_index].eq_index);
swap(MAX[index],MAX[size-1]);
RepDownMax(MAX,MIN,index,size-1);
}
void RemoveMin(Node*MAX,Node*MIN,int &size, int index){
swap(MAX[MIN[index].eq_index].eq_index,MAX[MIN[size-1].eq_index].eq_index);
swap(MIN[index],MIN[size-1]);
RepDownMin(MAX,MIN,index,size-1);
}
void CollatzMin( Node *MAX, Node *MIN, int &size){
if(*MIN[0].data%2==0){
*MIN[0].data/=2;
if(*MIN[0].data==1){
RemoveMin(MAX,MIN,size,0);
RemoveMax(MAX,MIN,size,MIN[size-1].eq_index);
size--;
}
else
RepDownMax(MAX,MIN,MIN[0].eq_index,size);
}
else{
long long int tmp=3*(*MIN[0].data)+1;
if(tmp>UINT_MAX){
*MIN[0].data=0;
RemoveMin(MAX,MIN,size,0);
RemoveMax(MAX,MIN,size,MIN[size-1].eq_index);
size--;
}
else {
*MIN[0].data=tmp;
RepUpMax(MAX,MIN,MIN[0].eq_index);
RepDownMin(MAX,MIN,0,size);
}
}
}
void CollatzMax( Node *MAX, Node *MIN, int &size){
if(*MAX[0].data%2!=0){
long long int tmp=3*(*MAX[0].data)+1;
if(tmp>UINT_MAX){
*MAX[0].data=0;
RemoveMax(MAX,MIN,size,0);
RemoveMin(MAX,MIN,size,MAX[size-1].eq_index);
size--;
}
else{
*MAX[0].data=tmp;
RepDownMin(MAX,MIN,MAX[0].eq_index,size);
}
}
else{
*MAX[0].data/=2;
if(*MAX[0].data==1){
RemoveMax(MAX,MIN,size,0);
RemoveMin(MAX,MIN,size,MAX[size-1].eq_index);
size--;
}
else
{
RepUpMin(MAX,MIN,MAX[0].eq_index);
RepDownMax(MAX,MIN,0,size);
}
}
}
int main() {
int ile,con=0,kom;
long long int tmp;
cin>>ile;
long long int *tablica=new long long int [ile];
Node *MaxHeap=new Node [ile];
Node *MinHeap=new Node [ile];
for(int i=0; i<ile; i++){
cin>>tmp;
if(tmp>UINT_MAX)
tablica[i]=0;
else if(tmp==1)
tablica[i]=1;
else if(tmp!=1){
tablica[i]=tmp;
DoNode(con,tablica+i,MaxHeap,MinHeap);
RepUpMax(MaxHeap,MinHeap,con);
RepUpMin(MaxHeap,MinHeap,con);
con++;
}
}
cin>>kom;
int ikom;
char wg;
for(int i=0; i<kom; i++){
cin>>ikom>>wg;
for(int j=0; j<ikom; j++){
if(wg=='s')
CollatzMin(MaxHeap,MinHeap,con);
else
CollatzMax(MaxHeap,MinHeap,con);
}
}
for(int i=0; i<ile; i++){
if(tablica[i]==0) cout<<"m ";
else
cout<<tablica[i]<<' ';
}
cout<<endl;
return 0;
}
W strukturze przechowuję wskaźnik dla element w tablicy oraz indeks tego samego elementu w drugim kopcu. Mogą Państwo mi powiedzieć, co tutaj może być źle? Pozdrawiam serdecznie.
C++ 