Cod sursa(job #227743)

Utilizator MciprianMMciprianM MciprianM Data 5 decembrie 2008 12:49:25
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<fstream>
using namespace std;
int arb[120000],n;
int poz,val;
int value, total,uth;
void update(int nod, int st, int dr){
  if(st<dr){
    int m=(st+dr)/2;
    if(poz<=m)
      update(nod*2, st, m);
    else update(nod*2+1, m+1,dr);
    arb[nod]=arb[nod*2]+arb[nod*2+1];
  }
  else arb[nod]+=val;
}
void query(int nod, int st, int dr){
  if(st==dr){poz=st;val=-1;update(1,1,n);return;}
  int m=(st+dr)/2;
  if(arb[nod*2]+uth<value){  uth+=arb[nod*2];query(nod*2+1, m+1, dr);}
  else query(nod*2,st,m);
}
int main(){
  int i;
  ifstream f("order.in");
  ofstream g("order.out");
  f>>n;
  f.close();
  val=1;
  for(i=0;i<n;i++){
    poz=i+1;
    update(1,1,n);
  }
  for(i=1,value=1,total=n;i<=n;i++){
    value=value+i;
    while(value>total)  value-=total;
    uth=0;
    query(1,1,n);
    total--;
    value--;
    g<<poz<<' ';
  }
  f.close();
  g<<'\n';
  g.close();
  return 0;
}