Cod sursa(job #1224651)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 31 august 2014 15:50:41
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<fstream>
using namespace std;
ifstream fi("order.in");
ofstream fo("order.out");

const int max_n = 30004;
const int max_nr_nod = 65540;//65536 = (1<<16);

int copii_stanga,last_player,poz_arb_current_player;
int i,n,arb[max_nr_nod];

void creare_arbore(int nod, int st, int dr){
     if(st==dr) arb[nod]=1;
     else{
          int mijl=(st+dr)/2;
          creare_arbore(2*nod,st,mijl);
          creare_arbore(2*nod+1,mijl+1,dr);
          arb[nod]=arb[2*nod]+arb[2*nod+1];
         }
}

void query(int nod, int st, int dr, const int &a, const int &b){
     if(a<=st && dr<=b){ copii_stanga+=arb[nod]; }
     else{
          int mijl=(st+dr)/2;
          if(a<=mijl) query(2*nod,st,mijl,a,b);
          if(mijl+1<=b) query(2*nod+1,mijl+1,dr,a,b);
         }
}

void update(int nod, int st, int dr, int nr){
     if(st==dr){ last_player=dr; fo<<dr<<" "; arb[nod]=0; }
     else{
          int mijl=(st+dr)/2;
          if(arb[2*nod]>=nr) update(2*nod,st,mijl,nr);
          else update(2*nod+1,mijl+1,dr,nr-arb[2*nod]);
          arb[nod]=arb[2*nod]+arb[2*nod+1];
         } 
}

int main(){
    fi>>n;
    
    creare_arbore(1,1,n);
    
    for(i=1,last_player=1;i<=n;i++)
       { 
        copii_stanga=0;                           
        query(1,1,n,1,last_player); 
                                  
        poz_arb_current_player=(copii_stanga+i)%arb[1];
        if(!poz_arb_current_player) poz_arb_current_player=arb[1];
        
        update(1,1,n,poz_arb_current_player);
       }
       
    fi.close();
    fo.close();
    return 0;
}