Cod sursa(job #1462481)

Utilizator mirupetPetcan Miruna mirupet Data 18 iulie 2015 11:48:10
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<cstdio>
#define LSB(x) (x & (-x))
using namespace std;
int N, avem;
int aib[30005];

void Update(int pos, int val)
{
    for ( int i = pos; i <= N; i += LSB(i))
        aib[i] += val;
}

inline int Query(int pos)
{
    int ans = 0, i;
    for (i = pos; i; i -= LSB(i))
        ans += aib[i];
    return ans;
}

int main()
    {
        int pos = 1, put, j, nr, i;
        freopen("order.in","r",stdin);
        freopen("order.out","w",stdout);

        scanf("%d", &N);
        for (i = 1; i<= N; i++)
            Update(i, 1);
        for ( put = 1; put < N; put <<= 1);

        for (i = 1; i <= N; i++)
        {
            avem = i % (N - i + 1);

            if ( !avem )
                avem = N - i + 1;

            nr = Query(N) - Query(pos);


            if (avem <= nr)
                nr = Query(pos) + avem;
            else
                nr = avem - nr;

            pos = 0;
            for (j = put; j; j >>= 1)
                if (j + pos < N && Query(j + pos) < nr)
                    pos += j;
            ++pos;
            printf("%d ", pos);
            Update(pos, -1);
        }
    }