Cod sursa(job #794570)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 6 octombrie 2012 16:00:15
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#define NMAx 120100
using namespace std;

int N,V[NMAx];

void Update(int Nod,int Left,int Right,int Dest,int Val) {

    if(Left==Right) {
        V[Nod]=Val;
        return;
        }

    int Mid=(Left+Right)>>1;

    if(Dest<=Mid)
        Update(2*Nod,Left,Mid,Dest,Val);
    else
        Update(2*Nod+1,Mid+1,Right,Dest,Val);

    V[Nod]=V[2*Nod]+V[2*Nod+1];

}
int Search(int Nod,int Left,int Right,int Val) {

    if(Left==Right)
        return Left;

    int Mid=(Left+Right)>>1;

    if(V[2*Nod]>=Val)
        return Search(2*Nod,Left,Mid,Val);
    else
        return Search(2*Nod+1,Mid+1,Right,Val-V[2*Nod]);

}
void Solve() {

    int i,Step,Start=2,Sol;
    ofstream out("order.out");

    for(i=1;i<=N;i++)
        Update(1,1,N,i,1);

    for(i=1,Step=Start;i<=N;i++) {

        Step=(Step+i-Start)%(N-i+1)+1;
        out<<(Sol=Search(1,1,N,Step))<<' ';
        Update(1,1,N,Sol,0);

        }

    out<<'\n';
    out.close();

}
void Citire() {

    ifstream in("order.in");
    in>>N;
    in.close();

}
int main() {

    Citire();
    Solve();

    return 0;

}