Cod sursa(job #1424664)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 25 aprilie 2015 11:35:05
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

int n, aib[300005], lim, a[300005], i, poz, nn, sol;

void update(int poz, int val)
{
    for(; poz <= n; poz += (poz & (-poz)))
        aib[poz] += val;
}
int query(int poz)
{
    int x = 0;
    for(int i = lim; i; i >>= 1)
        if(i + x <= n && aib[i + x] <= poz)
        {
            x += i;
            poz -= aib[x];
            if(!poz)
                break;
        }
    while(!a[x])x--;
    return x;

}
int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d", &n);
    for(lim = 1; lim <= n; lim <<= 1);
    for(i = 1; i <= n; i++)
    {
        update(i, 1);
        a[i] = 1;
    }
    poz = 2;
    for(i = 1; i <= n; i++)
    {
        nn = n - i + 1;
        poz = (poz + i - 1) % nn == 0 ? nn : (poz + i - 1) % nn;
        sol = query(poz);
        printf("%d ", sol);
        update(sol, -1);
        a[sol] = 0;
    }
    return 0;
}