Cod sursa(job #852518)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 11 ianuarie 2013 13:01:47
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
using namespace std;

int arbInt[1<<17 + 1];
// fiecare nod e 0/1 a fost sau nu eliminat copilul i
// eu tin suma pe intervale

int val, poz, raspuns;


void actualizeaza(int nod, int li, int ls){
   // actualizeaza nodul poz, cu informatia val
   if(li == ls){
     arbInt[nod] = val;
     return;
   }
   int mij = (li + ls) / 2;
   if(poz <= mij){
      actualizeaza(nod * 2, li, mij); // o iau in stanga  
   }else{
      actualizeaza(nod * 2 +1, mij + 1, ls);
   }
   
   arbInt[nod] = arbInt[nod * 2] + arbInt[nod * 2 +1]; // e suma celor doi fii ai sai
}


void cauta(int nod, int li, int ls){
    //cauta valoarea; pun raspunsul in raspuns
    if(li == ls){
      raspuns = li;
      return;
    }
    int mij = (li + ls) / 2;
    if(val <= arbInt[2 * nod]){ // daca imi ajunge ce e in stanga 
      cauta(2 * nod, li, mij);
    }else{
       val -= arbInt[2 * nod];
       cauta(2 * nod + 1, mij +1, ls);
    }
}


int main(){
   ifstream fin("order.in");
   ofstream fout("order.out");
   int n;
   fin>>n;
   int i;
   for(i = 1; i <= n; i++){
      val = 1;
      poz = i;
      actualizeaza(1,1,n); // nod, li, ls
   }

   int catiDeUnuInStanga = 2;
   
   for(i = 1; i <= n; i++){
      catiDeUnuInStanga = (catiDeUnuInStanga - 1 + i - 1)  % (n - i + 1) + 1; 
      // am cu 1 mai putin fata de ultima data, pentru ca pe unul tocmai l-am scos data trecuta
      // mai scad un 1, pentru ca adun un  la final; adun un unu la final, pentru ca modulul imi da de la 0
      // mai adun un 1 la a doua paranteza, pentru ca pana acum am eliminat doar i - 1 copii, deci mai am n - (i - 1) de 1
      val = catiDeUnuInStanga;
      cauta(1,1,n);
      fout<<raspuns<<" ";
      val = 0;
      poz = raspuns;
      actualizeaza(1,1,n);
   }

   return 0;
}