Cod sursa(job #1690936)

Utilizator mariakKapros Maria mariak Data 16 aprilie 2016 12:29:05
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
#define Nmax 30002
#define Log 15
FILE *fin  = freopen("order.in", "r", stdin);
FILE *fout = freopen("order.out", "w", stdout);

using namespace std;
int n, aib[Nmax];
void update(int pos, int val)
{
    do
    {
        aib[pos] += val;
        pos += pos & -pos;
    }
    while(pos <= n);
}
int bsearch(int x)
{
    int i = 0, p = 1 << Log;
    while(p)
    {
        if(i + p <= n && aib[i + p] < x)
        {
            i += p;
            x -= aib[i];
        }
        p >>= 1;
    }
    return i + 1;
}
int main()
{
    int i, k = 1, pos, m, c;
    scanf("%d", &n);
    m = n;
    for(i = 1; i <= n; ++ i)
        update(i, 1);
    pos = 2;
    c = 2;
    printf("%d ", c);
    update(c, -1);
    ++ k;
    -- m;
    while(m)
    {
        pos = (pos + k - 1) % m;
        if(!pos)
            pos = m;
        c = bsearch(pos);
        printf("%d ", c);
        update(c, -1);
        ++ k;
        -- m;
    }
    return 0;
}