Cod sursa(job #761434)

Utilizator vendettaSalajan Razvan vendetta Data 25 iunie 2012 22:56:49
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>

using namespace std;

#define nmax 30005

ifstream f("order.in");
ofstream g("order.out");

int n, a[nmax];
struct{

    int cnt;

}arb[nmax*4];

void citeste(){

    f >> n;

}

void udpate(int nod, int st, int dr, int poz, int val){

    if (st == dr){
        if (val == -1) arb[nod].cnt = 1;
        return;
    }

    int mij = ( st + dr) / 2;
    if (poz <= mij) udpate(nod*2, st, mij, poz, val);
            else udpate(nod*2+1, mij+1, dr, poz, val);

    arb[nod].cnt = arb[nod*2].cnt + arb[nod*2+1].cnt;

}

int afla_pozitie(int nod, int st, int dr, int x){

    if (st == dr){
        return st;
    }
    int mij = (st + dr) / 2;
    if (mij - st + 1 -arb[nod*2].cnt >= x)
        return afla_pozitie(nod*2,st, mij, x);
    else return afla_pozitie(nod*2+1, mij+1, dr, x-mij+st-1+arb[nod*2].cnt);

}

void rezolva(){

    for(int i=1; i<=n; i++){
        a[i] = i;
    }

    g << 2 << " ";
    udpate(1,1,n,2,-1);
    int prec = 2;
    for(int i=2; i<=n; i++){
        prec = ( prec + i -1 ) % (n-i+1);
        if (prec == 0) prec = n-i+1;
        int poz = afla_pozitie(1,1,n,prec);
        udpate(1,1,n,poz,-1);
        g << a[poz] << " ";
    }

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

}