Cod sursa(job #1768311)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 30 septembrie 2016 17:49:27
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#include <stdlib.h>
#define zeros(x) (((x-1)^x)&x)
#define MAXN 30000

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

int aib[MAXN+1],n;
inline void add(int poz,int nr){
    for(int i=poz;i<=n;i+=zeros(i))
        aib[i]+=nr;
}
inline int sum(int poz){
    int s=0;
    for(int i=poz;i>0;i-=zeros(i))
        s=s+aib[i];
    return s;
}

int main(){
    fi=fopen("order.in","r");
    fo=fopen("order.out","w");
    int i,x,poz,st,dr,mij;
    n=nextnum();
    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(fo,"%d " ,x);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}