Cod sursa(job #1764418)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 25 septembrie 2016 15:11:11
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define N 30010

using namespace std;

int viz[N];
int sol[N];
int arb[N];
int n;

void update(int nod, int val){

    viz[nod]=val;
    while(nod<=n){
        arb[nod]+=val;
        nod= nod+( nod ^ (nod & (nod-1) )    );
    }

}

int sum(int x){
    static int s;

    s=0;
    while(x>0){
        s+=arb[x];
        x=x&(x-1);
    }
    return s;
}


int srch(int lf, int val){
    static int mid,smid,rf;

    rf=n;
    while(lf<=rf){
        mid=(lf+rf)/2;
        smid=sum(mid);
        if(smid<val){
            lf=mid+1;
        }else if(smid>val){
            rf=mid;
        }else{
            while(viz[mid]==-1){
                mid--;
            }
            return mid;
        }

    }
    return -1;
}

int main(){
    int i,k,p,cnt;
    int sumk,sumn,step;
    int lf;

    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);

    scanf("%d",&n);

    for(i=1;i<=n;i++){
        update(i,1);
    }


    k=1;
    p=1;
    cnt=1;
    while(cnt<=n){
        sumk=sum(k);
        sumn=sum(n);
        step=p%sumn;
        if(step){
            if(step>sumn-sumk){
                lf=1;
                step+=sumk;
                step%=sumn;
            }else {
                lf=k;
                step+=sumk;
                //step=step-(sumn-sumk);
            }

        }else{
            step=sumk;
            if(step){
                lf=1;
            }else{
                lf=k;
                step=sumn;
            }
        }
        k=srch(lf,step);
        sol[cnt++]=k;
        update(k,-1);
        p++;
    }

    for(i=1;i<=n;i++){
        printf("%d ",sol[i]);
    }

    return 0;
}