Cod sursa(job #551411)

Utilizator acelasi7Tudor Maxim acelasi7 Data 10 martie 2011 19:14:46
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
using namespace std;

#define nrn 60010

FILE *in=fopen("order.in","r"),*out=fopen("order.out","w");

int TREE[nrn],ord[nrn/2];
int build(int lf,int rt,int nod)
{
    if(lf==rt)
        TREE[nod]=1;
    else{
    int mid=(lf+rt)/2;
    TREE[nod]=build(lf,mid,nod*2)+build(mid+1,rt,nod*2+1);
    }
    return TREE[nod];
}
int search(int nod,int lf,int rt,int val)
{
    TREE[nod]--;
    if(lf==rt)
        return lf;
    int mid=(lf+rt)/2;
    if(val<=TREE[nod*2])
        return search(nod*2,lf,mid,val);
    return search(nod*2+1,mid+1,rt,val-TREE[nod*2]);
    TREE[nod]=TREE[nod*2]+TREE[nod*2+1];
}
int main()
{
    int x=1,i,n,poz;
    fscanf(in,"%d",&n);
    build(1,n,1);
    for(i=1;i<=n;++i)
    {
        x=(x+i)%(n-i+1);
        if(!x)
            x=n-i+1;
        poz=search(1,1,n,x);
        fprintf(out,"%d ",poz);
        --x;
        if(!x)
            x=n-i;
    }
    return 0;
}