Cod sursa(job #1066963)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 25 decembrie 2013 21:44:42
Problema Hashuri Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.7 kb
//O alternativa pentru AVL-uri sau Treapuri si in general a arborilor echilibrati de cautare in timp de concurs
//Complexitatea medie pe orice operatie este O( log N )
//Skip lists
#include<fstream>
#include<stdlib.h>
using namespace std;
typedef struct celula {
              int val;
              celula *next, *low;
              }*lista;
lista head, drum[50];
int op,i,n,x,ld;

int inaltime(){
    int h=0,coin=rand()%2;
    while (coin) {
          ++h;
          coin=rand()%2;
          }
    return(h);
}

void init() {
     head=new celula;
     head->val=-1; head->low=0; head->next=0;
     int k=inaltime();
     for (int i=1; i<=k; ++i) {
         lista v=new celula;
         v->val=head->val;
         v->low=head;
         v->next=0;
         head=v;
         }
}

void cauta(int x) {
     lista aux=head;
     ld=0;
     while (aux!=0)
           if (aux->next!=0&&aux->next->val<=x) aux=aux->next;
            else {
                 ++ld;
                 drum[ld]=aux;
                 aux=aux->low;
                 }
}

void insereaza(int x) {
     cauta(x);
     if (drum[ld]->val!=x) {
                           int k=inaltime();
                           if (k==0) ++k;
                           lista prec=0,v;
                           for (int i=1; i<=k; ++i) 
                            if (ld>0) {
                                      lista v=new celula;
                                      v->val=x;
                                      v->low=prec;
                                      v->next=drum[ld]->next;
                                      drum[ld]->next=v;
                                      --ld; prec=v;
                                      }
                            else {
                                 v=new celula; v->val=head->val;
                                 v->low=head; head=v;
                                 v=new celula; v->val=x; v->next=0;
                                 v->low=prec; head->next=v;
                                 prec=v;
                                 }
                            }
}

void sterge(int x) {
     cauta(x-1);
     while (ld>0&&drum[ld]->next!=0&&drum[ld]->next->val==x) {
             drum[ld]->next=drum[ld]->next->next;
             --ld;
             }
}

bool exista(int x) {
     cauta(x);
     return( drum[ld]->val==x );
}

int main(void) {
    ifstream fin("hashuri.in");
    ofstream fout("hashuri.out");
    fin>>n; init(); srand(time(NULL));
    for (i=1; i<=n; ++i) {
          fin>>op>>x;
          if (op==1) insereaza(x);
          else if (op==2) sterge(x);
           else fout<<exista(x)<<"\n";
           }
  return(0);
}