Cod sursa(job #908669)

Utilizator cont_testeCont Teste cont_teste Data 9 martie 2013 21:42:44
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb

#include<cstdio>

#define NMAX 30005
#define lsb(x) x&(-x)

FILE *f=fopen("order.in","r");
FILE *g=fopen("order.out","w");

using namespace std;

int AIB[NMAX],N;

void Update(int nod,int val)
{
    for(;nod<=N;nod+=lsb(nod))
       AIB[nod]+=val;
}
int Query(int nod)
{
    int sum=0;
    for(;nod>=1;nod-=lsb(nod))
        sum+=AIB[nod];
    return sum;
}

int bs(int val)
{
int left=1,right=N,mid;
int res;
while(left <= right)
{
    mid=left+((right-left)>>1);
    int ok=Query(mid);
    if( ok == val )
        res=mid;
    if(ok < val)
        left=mid+1;
    else
        right=mid-1;
}
return res;



}


int main()
{
    int a=1,nr;
    fscanf(f,"%d",&N);
    for(int i(1); i <= N;  i++ )
        Update(i,1);
    nr=N;
    for(int i(1); i <= N; ++i)
    {
     a+=i;
     a%=nr;
     if(a==0)
        a=nr;
        int q=bs(a);
     fprintf(g,"%d ",q);
      Update(q,-1);
      a--;
      nr--;

    }
    fclose(f);
    fclose(g);
    return 0;

}