Cod sursa(job #789287)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 17 septembrie 2012 18:58:12
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>

#define MAX 32768
#define left (nod << 1)
#define right ((nod << 1) + 1)

using namespace std;

int aInt[4 * MAX], poz, aux, T, n;

void build(int nod, int l, int r)
{
    if(l == r)
    {
        aInt[nod] = 1;
        return;
    }
    int m = (l + r) >> 1;
    build(left, l, m);
    build(right, m + 1, r);
    aInt[nod] = aInt[left] + aInt[right];
}

int query(int nod, int l, int r)
{
    if(l == r)
        return l;
    int m = (l + r) >> 1;
    if(aInt[left] >= aux)
        return query(left, l, m);
    else
    {
        aux -= aInt[left];
        return query(right, m + 1, r);
    }
}

void update(int nod, int l, int r)
{
    if(l == r)
    {
        aInt[nod]--;
        return;
    }
    int m = (l + r) >> 1;
    if(poz <= m)
        update(left, l, m);
    else
        update(right, m + 1, r);
    aInt[nod] = aInt[left] + aInt[right];
}

int main()
{
    ifstream in("order.in"); in>>n; in.close();
    build(1, 1, n);
    ofstream out("order.out");
    T = 1;
    for(int i = 1; i <= n; i++)
    {
        T = (T + i) % aInt[1];
        if(!T) T = aInt[1];
        aux = T;
        poz = query(1, 1, n);
        out<<poz<<" ";
        update(1, 1, n);
        T--;
        if(!T) T = aInt[1];
    }
    return 0;
}