Cod sursa(job #1423714)

Utilizator AndyCatrunaCatruna Andy AndyCatruna Data 22 aprilie 2015 13:55:56
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#define dim 30005
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n,i,r,v[4*dim],c,P;
void build(int nod,int p,int u){
    if(p==u){
        v[nod]=1;
        return;
    }else{
        int mid=(p+u)/2;
        build(2*nod,p,mid);
        build(2*nod+1,mid+1,u);
        v[nod]=v[2*nod]+v[2*nod+1];
    }
}
void update(int nod,int p, int u,int poz){
    if(p==u){
        v[nod]=0;
        return;
    }
    int  mid=(p+u)/2;
    if(mid>=poz){
        update(2*nod,p,mid,poz);
    }
    else{
        update(2*nod+1,mid+1,u,poz);
    }
    v[nod]=v[2*nod]+v[2*nod+1];
}
int query(int nod,int p,int u,int val){
    if(p==u){
        return u;
    }
    int mid=(p+u)/2;
    if(v[2*nod]>=val){
        return query(2*nod,p,mid,val);
    }
    else{
        return query(2*nod+1,mid+1,u,val-v[2*nod]);
    }
}
int main(){
    fin>>n;
    build(1,1,n);
    r=n;
    c=1;
    for(i=1;i<=n;i++){
        c+=i;
        c%=r;
        if(c==0){
            c=r;
        }
        P=query(1,1,n,c);
        fout<<P<<" ";
        update(1,1,n,P);
        c--;r--;
    }

    return 0;
}