Cod sursa(job #1537555)

Utilizator akaprosAna Kapros akapros Data 27 noiembrie 2015 15:39:24
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>
#define maxN 30002
using namespace std;
int n, m, sum, arb[maxN * 4], pos, val, q;
void update(int node, int l, int r)
{
    if (l == r)
    {
        arb[node] += val;
        return ;
    }
    int lson = 2 * node, rson = 2 * node + 1, mid = (l + r) >> 1;
    if (pos <= mid)
        update(lson, l, mid);
    else
        update(rson, mid + 1, r);
    arb[node] = arb[lson] + arb[rson];
}
void query(int node, int l, int r)
{
    if (1 <= l && q >= r)
    {
        sum += arb[node];
        return ;
    }
    int lson = 2 * node, rson = lson + 1, mid = (l + r) >> 1;
    if (1 <= mid && q >= l)
        query(lson, l, mid);
    if (1 <= r && q >= mid + 1)
        query(rson, mid + 1, r);
}
void read()
{
    freopen("order.in", "r", stdin);
    scanf("%d", &n);
}
int bs(int x)
{
    int i = 0, p = 1 << 14;
    while (p)
    {
        sum = 0;
        if (i + p <= n)
        {
            q = i + p;
            query(1, 1, n);
            if (sum < x)
                i += p;
        }
        p /= 2;
    }
    return i + 1;
}
void solve()
{
    int i;
    m = n;
    for (i = 1; i <= n; ++ i)
    {
        pos = i;
        val = 1;
        update(1, 1, n);
    }
}
void write()
{
    int i, p, s = 1;
    freopen("order.out", "w", stdout);
    for (i = 1; i <= n; ++ i)
    {
        s = (s + i) % m;
        if (s == 0)
            s = m;
        printf("%d ", p = bs(s));
        pos = p;
        val = -1;
        update(1, 1, n);
        -- m;
        -- s;
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}