Cod sursa(job #1146755)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 19 martie 2014 11:32:20
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#define ub(x) (x&(-x))

using namespace std;
int a[30009],n,i,j,poz,p,mod,st,dr,mij,val,sol;


int Q(int x)
{
   int s=0;
   for(x=x;x>0;x-=ub(x))
   s+=a[x];
   return s;

}

void update(int x,int y)
{
   for(x=x;x<=n;x+=ub(x))
   a[x]+=y;
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);

    scanf("%d",&n);


    for(i=1;i<=n;++i) update(i,1);

    p=2;
    for(i=1;i<=n;++i)
    {
       mod=n-i+1;
       p=(p+i-1)%mod;
       if(!p) p=mod;
       st=1;
       dr=n;
       while(st<=dr)
       {
          mij=(st+dr)/2;
          val=Q(mij);
          if(val<p) st=mij+1;
          else if(val>p) dr=mij-1;
          else
          {
            sol=mij;
            dr=mij-1;
          }

       }

       printf("%d ",sol);
       update(sol,-1);


    }

    printf("\n");



    return 0;
}