Cod sursa(job #1601840)

Utilizator andytosaAndrei Tosa andytosa Data 16 februarie 2016 11:48:36
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <iostream>
#define L 30000
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");

int v[4 * L], f[4 * L];
int n, pos, val, nrR, nrC, d, aux;

void update(int nod, int left, int right){
    if(left == right){
        v[nod] += val;
        f[nod] = pos;
        return;
    }

    int mij = (left + right) / 2;
    if(pos <= mij)
        update(2 * nod, left, mij);
    else
        update(2 * nod + 1, mij + 1, right);

    v[nod] += val;
}

void find_pos(int x, int nod)
{
    if (f[nod] != 0)
    {
        pos = nod;
        return;
    }
    if (x <= v[nod * 2])
        find_pos(x, nod * 2);
    else
        find_pos(x - v[nod * 2], nod * 2 + 1);
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i){
        pos = i;
        val = 1;
        update(1, 1, n);
    }

    nrR = n;
    nrC = 1;
    d = 1;
    val = -1;
    while (nrR)
    {
        aux = (nrC + d) % nrR;
        if(aux == 0) aux = 1;
        find_pos(aux,1);
        fout << f[pos] << " ";

        pos = f[pos];
        update(1, 1, n);

        nrC = aux - 1;
        nrR--;
        d++;
    }

    return 0;
}