Cod sursa(job #1183181)

Utilizator livliviLivia Magureanu livlivi Data 8 mai 2014 16:39:54
Problema Order Scor 90
Compilator cpp Status done
Runda aib-uri Marime 1.07 kb
#include<cstdio>
#define ub(x) (x&(-x))
using namespace std;
int aib[30001];
int n;
int c[30001];
void add(int x,int y){
    int i;
    for(i=x;i<=n;i+=ub(i))
        aib[i]+=y;
}
int sum(int x){
    int i,s=0;
    for(i=x;i>0;i-=ub(i))
        s+=aib[i];
    return s;
}
int cb(int x,int in){
    int sf=n,m,k,y=sum(in-1);
    while(in<sf){
        m=(in+sf)/2;
        k=sum(m)-y;
        if (k<x) in=m+1;
        else sf=m;
    }
    if (sum(sf)-y==x){
        while(sf<=n &&c[sf]==1) sf++;
        if (sf==n+1){
            sf=1;
            while(sf<=n &&c[sf]==1) sf++;
        }
        return sf;
    }
    return cb(x-(sum(n)-y),1);
}
int main(){
    freopen ("order.in","r",stdin);
    freopen ("order.out","w",stdout);
    int i,k;
    scanf ("%d",&n);
    for(i=1;i<=n;i++)
        add(i,1);
    printf ("2 ");
    add(2,-1);
    c[2]=1;
    k=2;
    for(i=2;i<=n;i++){
        if (k==n) k=0;
        k=cb(i,k+1);
        while(c[k]==1) k++;
        printf ("%d ",k);
        c[k]=1;
        add(k,-1);
    }
    return 0;
}