Cod sursa(job #1423707)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 22 aprilie 2015 13:29:03
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#define DIM 30002

using namespace std ;

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

int N;
int v[4*DIM];
int r;
int cnt;
void build(int nod,int p,int u){
    if(p==u){
        v[nod]=1;
        return;
    }
    int mid=(p+u)>>1;
    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)>>1;
    if(poz<=mid)
        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 p;
    }
    int mid=(p+u)>>1;
    if(val<=v[2*nod])
        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;
    cnt=1;
    for(int i=1;i<=N;i++){
        cnt+=i;
        cnt%=r;
        if(cnt==0)
            cnt=r;
        int poz=query(1,1,N,cnt);
        fout<<poz<<" ";
        update(1,1,N,poz);
        r--;
        cnt--;
    }
    fin.close();fout.close();
    return 0;
}