Cod sursa(job #1680019)

Utilizator SmarandaMaria Pandele Smaranda Data 8 aprilie 2016 14:29:24
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>

using namespace std;

const int N = 30002;

int aib [N], n;

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

void update (const int &poz, const int &value) {
    int i;

    for (i = poz; i <= n; i = i + lsb (i))
        aib [i] = aib [i] + value;
}

int query (const int &poz) {
    int ans = 0, i;

    for (i = poz; i >= 1; i = i - lsb (i))
        ans = ans + aib [i];
    return ans;
}

int query2 (const int &value) {
    int i, step, x;

    x = value;
    for (i = 0, step = (1 << 15); step; step >>= 1)
        if (i + step <= n && aib [i + step] < x) {
            i = i + step;
            x = x - aib [i];
        }
    ++ i;
    if (query (i) == value)
        return i;
    return 0;
}

int main () {
    int i, total, k, last, poz;

    freopen ("order.in", "r", stdin);
    freopen ("order.out", "w", stdout);

    scanf ("%d", &n);
    for (i = 1; i <= n; i ++)
        update (i, 1);
    total = n;
    last = 1;
    for (i = 1; i <= n; i ++) {
        if (total == 0)
            break;
        poz = query2 (last + i);
        if (poz) {
            printf ("%d ", poz);
            last = query (poz) - 1;
            update (poz, -1);
            total --;
        }
        else {
            k = total - last;
            k = i - k;
            k = k % total;
            if (k == 0)
                k = total;
            poz = query2 (k);
            printf ("%d ", poz);
            last = query (poz) - 1;
            update (poz, -1);
            total --;
        }
    }
    printf ("\n");
    return 0;
}