Cod sursa(job #1805033)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 13 noiembrie 2016 13:21:48
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>

using namespace std;

int logn,aib[30010],n;

void aib_update(int poz,int x)
{
    for(int i=poz;i<=n;i+=i&(-i)) aib[i]+=x;
}

int aib_query(int poz)
{
    int s=0;
    for(int i=poz;i>=1;i-=i&(-i)) s+=aib[i];
    return s;
}

int aib_cauta(int a)
{
     int poz=0;
        for(int i=logn;i>=0;i--)
            if(poz+(1<<i)<=n && aib[poz+(1<<i)]<a)
            {
                poz+=1<<i;
                a-=aib[poz];
            }
     return poz+1;
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int k=2,r;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) aib_update(i,1);
    for(logn=1;(1<<logn)<=n;logn++);
    logn--;
    for(int j=2;j<=n;j++)
    {
        r=aib_cauta(k);
        aib_update(r,-1);
        printf("%d ",r);
        k=(k-1+j)%(n-j+1);
        if(k==0) k=n-j+1;
    }
    r=aib_cauta(k);
    printf("%d",r);
    return 0;
}