Cod sursa(job #1153114)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 25 martie 2014 11:34:03
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>

using namespace std;

int n, v[30010];

void update (int poz, int val)
{
    for (int i = poz; i <= n; i += i & (-i))
        v[i] += val;
}

int sum (int poz)
{
    int rez = 0;
    for (int i = poz; i; i -= i & (-i))
        rez += v[i];

    return rez;
}

int cautbin (int x)
{
    int a = 1, b = n;
    while (a <= b)
    {
        int m = (a + b) / 2;
        int s = sum (m);

        if (s == x) return m;
        else if (s > x) b = m - 1;
        else a = m + 1;
    }
}

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 summ = 1, x = 1, nrm = n, p;
    for (int i = 1; i < n; i++)
    {
        int y = i % nrm;

        if (i > 1) summ = sum (p);

        int x = y + summ;
        x %= nrm;

        if (!x) x = nrm;
        p = cautbin (x);

        printf ("%d ", p);
        update (p, -1);
        nrm--;
    }

    p = cautbin (1);
    printf ("%d", p);

    return 0;
}