Cod sursa(job #1419804)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 16 aprilie 2015 16:21:59
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#define DIM 30002

using namespace std;

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

int Tree[ 4 * DIM ];
int N , queue , remaining_kids ;
void build(int nod,int p,int u){
    if(p==u){
        Tree[nod]=1;
        return;
    }
    int mid=(p+u)>>1;
    build(2*nod,p,mid);
    build(2*nod+1,mid+1,u);
    Tree[nod]=Tree[2*nod]+Tree[2*nod+1];
}
void update(int nod,int p,int u,int poz,int val){
    if(p==u){
        Tree[nod]=val;
        return;
    }
    int mid=(p+u)>>1;
    if(poz<=Tree[2*nod])
        update(2*nod,p,mid,poz,val);
    else
        update(2*nod+1,mid+1,u,poz-Tree[2*nod],val);
    Tree[nod]=Tree[2*nod]+Tree[2*nod+1];
}
int Query(int nod,int p,int u,int poz){
    if(p==u){
        return p;
    }
    int mid=(p+u)>>1;
    if(poz<=Tree[2*nod])
        return Query(2*nod,p,mid,poz);
    else
        return Query(2*nod+1,mid+1,u,poz-Tree[2*nod]);
}
int main(){
    fin>>N;
    build(1,1,N);
    queue=2;
    remaining_kids=N;
    for(int i=1;i<=N;i++){

        queue=(queue+i-1)%remaining_kids;
        if(!queue)
            queue=remaining_kids;
        int poz=Query(1,1,N,queue);
        fout<<poz<<" ";
        update(1,1,N,queue,0);
        remaining_kids--;
    }
    fin.close();fout.close();
    return 0;
}