Cod sursa(job #1220010)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 16 august 2014 12:31:29
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<fstream>
using namespace std;
int aint[150000],i,p,n,sum,x,y;

void init(int nod, int l, int r) {
  if (l==r) aint[nod]=1;
  else {
       int mid=(l+r)/2;
       init(2*nod,l,mid);
       init(2*nod+1,mid+1,r);
       aint[nod]=aint[2*nod]+aint[2*nod+1];
       }
}

void update(int nod, int l, int r) {
     if (l==r) --aint[nod];
     else {
          int mid=(l+r)/2;
          if (p<=mid) update(2*nod,l,mid);
          else update(2*nod+1,mid+1,r);
          aint[nod]=aint[2*nod]+aint[2*nod+1];
          }
}

void query(int nod, int l, int r) {
  if (l>=x&&r<=y) sum+=aint[nod];
  else {
       int mid=(l+r)/2;
       if (x<=mid) query(2*nod,l,mid);
       if (y>mid) query(2*nod+1,mid+1,r);
       }
}

int cauta(int nod, int l, int r, int val) {
   if (l==r) return l;
   else {
        int mid=(l+r)/2;
        if (aint[2*nod]>=val) return cauta(2*nod,l,mid,val);
        else return cauta(2*nod+1,mid+1,r,val-aint[2*nod]);
        }
}

int main(void) {
    ifstream fin("order.in");
    ofstream fout("order.out");
    
    fin>>n;
    init(1,1,n);
    
    i=1;
    p=2;
    int nrt=n;
    
    while (nrt>1) {
          fout<<p<<" ";
          update(1,1,n);
          --nrt;
          ++i;
          
          sum=0;
          x=p; y=n;
          query(1,1,n);
          int sum1=sum;
          
          sum=0;
          x=1; y=p;
          query(1,1,n);
          
          int next=i%nrt;
          if (next==0) next=nrt;
          
          if (sum1>=next) p=cauta(1,1,n,sum+next);
          else p=cauta(1,1,n,next-sum1);
          
          }
   
   fout<<p;
    
   return 0;   
}