Cod sursa(job #1292669)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 14 decembrie 2014 16:48:15
Problema Order Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <stdio.h>
#define MAXN 30000
#define LOGN 15
#define MAXP (1<<(LOGN+1))
int t[MAXP];
int poz, val;
void update(int p, int st, int dr){
    int m=(st+dr)/2;
    t[p]--;
    if(st==dr){
        poz=st;
        return ;
    }
    if(val>t[2*p+1]){
        val-=t[2*p+1];
        update(2*p+2, m+1, dr);
    }else{
        update(2*p+1, st, m);
    }
}
int query(int p, int st, int dr){
    int m=(st+dr)/2, s=0;
    if(st>poz){
        return t[p];
    }
    if(m>poz){
        s=query(2*p+1, st, m);
    }
    return s+query(2*p+2, m+1, dr);
}
void dfs(int p, int st, int dr){
    int m=(st+dr)/2;
    t[p]=dr-st+1;
    if(st!=dr){
        dfs(2*p+1, st, m);
        dfs(2*p+2, m+1, dr);
    }
}
int main(){
    int n, i, add, x;
    FILE *fin, *fout;
    fin=fopen("order.in", "r");
    fout=fopen("order.out", "w");
    fscanf(fin, "%d", &n);
    dfs(0, 1, n);
    poz=1;
    for(i=1; i<n; i++){
        add=1+(i-1)%t[0];
        x=query(0, 1, n);
        if(x>=add){
            val=t[0]-x+add;
        }else{
            val=add-x;
        }
        update(0, 1, n);
        fprintf(fout, "%d ", poz);
    }
    val=1;
    update(0, 1, n);
    fprintf(fout, "%d\n", poz);
    fclose(fin);
    fclose(fout);
    return 0;
}