Cod sursa(job #1425375)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 27 aprilie 2015 13:11:06
Problema Order Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 1.25 kb
#include <cstdio>

using namespace std;

const int nmax=30000;

int n;
int aib[nmax+5];
int sol[nmax+5];

inline int lsb(int x)
{
    return x&-x;
}

void update(int pos, int val)
{
    for(int i=pos; i<=n; i+=lsb(i))
        aib[i] += val;
}

int querry(int pos)
{
    int ans=0;
    for(int i=pos; i>0; i-=lsb(i))
        ans+=aib[i];
    return ans;
}

int binary(int x, int y, int val)
{
    int last;
    int ans = 0, sc = 0;
    int t=querry(x-1);
    for(int i=1<<17; i>0; i>>=1)
        if(ans+i<=n)
        {
            if(sc+aib[ans+i]-t<val)
            {
                ans+=i;
                sc+=aib[ans];
            }
            else if(sc+aib[ans+i]-t==val)
                last=ans+i;
        }
    return last;
}

int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        update(i, 1);
    int pos = 1;
    for(int i=1; i<=n; i++)
    {
        int lg = (i-1) % (n-i+1) + 1;
        int limit = querry(n) - querry(pos);
        if(lg<=limit)
            pos = binary(pos+1, n, lg);
        else pos = binary(1, pos, lg-limit);
        update(pos, -1);
        printf("%d ", pos);
    }
    return 0;
}