Cod sursa(job #1776517)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 11 octombrie 2016 14:46:37
Problema Order Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia2-arborideintervale Marime 0.82 kb
#include<cstdio>
#define MAXN 30010
using namespace std;
int aib[MAXN],n;
void Update(int x,int value){
    for(x;x<=n;x=x+((x&(x-1))^x))
        aib[x]+=value;
}
int Query(int x){
    int step,answer=0;
    for(step=1;step<=n;step*=2);
    for(step;step>0;step/=2)
        if(answer+step<=n&&aib[answer+step]<x){
            x-=aib[answer+step];
            answer+=step;
        }
    return answer+1;
}
int main(){
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int i,x,value;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        Update(i,1);
    Update(2,-1);
    printf("2 ");
    x=2;
    for(i=2;i<=n;i++){
        x=(x+i-1)%(n-i+1);
        if(x==0)
            x=n-i+1;
        value=Query(x);
        printf("%d ",value);
        Update(value,-1);
    }
    return 0;
}