Cod sursa(job #1427257)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 1 mai 2015 20:12:57
Problema Order Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <stdlib.h>
#define zeros(x) (((x-1)^x)&x)
#define MAXN 30001
int aib[MAXN],n;
inline void add(int poz,int nr){
    int i;
    for(i=poz;i<=n;i+=zeros(i))
        aib[i]+=nr;
}
inline int sum(int poz){
    int i,s=0;
    for(i=poz;i>0;i-=zeros(i))
        s=s+aib[i];
    return s;
}
int main(){
    FILE*fi,*fout;
    int i,x,poz,st,dr,mij;
    fi=fopen("order.in" ,"r");
    fout=fopen("order.out" ,"w");
    fscanf(fi,"%d" ,&n);
    for(i=1;i<=n;i++)
        add(i,1);
    poz=2;
    for(i=1;i<=n;i++){
        poz=(poz+i-1)%(n-i+1);
        if(poz==0)
            poz=n-i+1;
        st=1;
        x=dr=n;
        while(st<=dr){
            mij=(st+dr)/2;
            if(sum(mij)<=poz){
                x=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        while(sum(x)==poz)
            x--;
        x++;
        add(x,-1);
        fprintf(fout,"%d " ,x);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}