Cod sursa(job #1619296)

Utilizator bullracerGabriel bullracer Data 28 februarie 2016 14:58:36
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>

#define NMAX 80007

using namespace std;

ifstream cin("order.in");
ofstream cout("order.out");

int Arbi[NMAX];
int poz, n, Nr, Val;

void update(int Node, int st, int dr){
    if(st == dr){
        Arbi[Node] = Val;
        return ;
    }
    int med = (st + dr) >> 1;
    if(poz <= med)
        update(2 * Node , st , med);
    if(poz > med)
        update(2 * Node + 1 , med + 1 , dr);
    Arbi[Node] = Arbi[2 * Node] + Arbi[2 * Node + 1];
}

void query(int Node, int st, int dr, int Nr){
    if(st == dr){
        poz = st;
        return ;
    }
    int med = (st + dr) >> 1;
    if(Nr <= Arbi[2 * Node])
        query(2 * Node, st, med, Nr);
    if(Nr > Arbi[2 * Node])
        query(2 * Node + 1, med + 1, dr, Nr - Arbi[2 * Node]);
}

int main(){
    cin >> n;
    Val = 1;
    for(int i = 1 ; i <= n ; ++ i)
        poz = i , update(1, 1, n);
    Val = 0;
    Nr = 1;
    for(int i = 1 ; i <= n ; ++ i){
        Nr = (Nr + i) % Arbi[1];
        if(Nr == 0)
            Nr = Arbi[1];
        query(1, 1, n, Nr);
        cout << poz << " ";
        --Nr;
        update(1 , 1 , n);
    }
    return 0;
}