Cod sursa(job #1220008)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 16 august 2014 12:20:21
Problema Order Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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 st, int dr, int val) {
   int l=st,r=dr; 
   
   while (l<=r) {
         int mid=(l+r)/2;
         sum=0;
         x=st; y=mid;
         query(1,1,n);
         
         if (sum>=val) r=mid-1;
         else l=mid+1;
         }    
   
   return l;
}

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 next=i%nrt;
          if (next==0) next=nrt;
          
          if (sum>=next) p=cauta(p+1,n,next);
          else p=cauta(1,n,next-sum);
          
          }
   
   fout<<p;
    
   return 0;   
}