Cod sursa(job #883329)

Utilizator Theorytheo .c Theory Data 19 februarie 2013 22:04:23
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<fstream>

using namespace std;

#define Nmax 30005
#define LeftSon (Nod << 1)
#define RightSon (Nod << 1) + 1

ifstream fin("order.in");
ofstream fout("order.out");

int N; int A[Nmax << 2];

void Build(int Nod, int st, int dr){

    if(st == dr) { A[Nod] = 1;return ;}

    int m = (st + dr) >> 1;
    Build(LeftSon, st, m );
    Build(RightSon, m + 1, dr);
    A[Nod] = A[LeftSon] + A[RightSon];
}

int Query(int Nod, int st, int dr, int Val){

    if(st == dr) return st;

    int m = (st + dr) >> 1;

    if(Val <= A[LeftSon]) Query(LeftSon, st, m, Val);
    else    Query(RightSon, m + 1, dr, Val - A[LeftSon]);
}

void Update(int Nod, int st, int dr, int pos){

    if(st == dr) {A[Nod] = 0; return;}

    int m = (st + dr) >> 1;

    if(pos <= m )   Update(LeftSon, st, m, pos);
    else Update(RightSon, m + 1, dr, pos);

    A[Nod] = A[LeftSon] + A[RightSon];
}

int main(){

    fin >>N;
    int T = 1; Build(1, 1, N);
    for(int i = 1; i <= N; ++i){
        T = (T + i) % A[1];
        if(!T) T = A[1];

        int pos = Query(1, 1, N, T);
        fout << pos <<" ";
        Update(1, 1, N, pos);
        --T; if(!T) T = A[1];
    }
    return 0;
}