Cod sursa(job #1368366)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 2 martie 2015 16:36:45
Problema Order Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#define N 30000
int v[N+1],n;
void update(int poz,int val){
    int cont=0;
    while(poz<=n){
        v[poz]+=val;
        while((poz&(1<<cont))==0)
            cont++;
        poz+=(1<<cont);
        cont++;
    }
}
int sum(int poz){
    int s=0,cont=0;
    while(poz){
        s+=v[poz];
        while((poz&(1<<cont))==0)
            cont++;
        poz-=(1<<cont);
        cont++;
    }
    return s;
}
int caut(int val){
    int st=1,dr=n;
    while(st<=dr){
        int mij=(st+dr)/2;
        if(sum(mij)<val)
            st=mij+1;
        else
            dr=mij-1;
    }
    return st;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("order.in","r");
    fout=fopen("order.out","w");
    fscanf(fin,"%d",&n);
    int i;
    for(i=1; i<=n; i++)
        update(i,1);
    int poz=1;
    for(i=1; i<=n; i++){
        poz=(poz+i)%(n-i+1);
        if(poz==0)
            poz=n-i+1;
        int p=caut(poz);
        fprintf(fout,"%d ",p);
        update(p,-1);
        poz=sum(p);
    }
    return 0;
}