Cod sursa(job #1292616)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 14 decembrie 2014 15:39:48
Problema Farfurii Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#define MAXN 100000
#define LOGN 17
#define MAXP (1<<(LOGN+1))
int t[MAXP];
int ans;
long long k;
inline long long invmax(long long x){
    return x*(x-1)/2LL;
}
void update(int p, int st, int dr, int sum){
    int m=(st+dr)/2;
    if(st==dr){
        ans=st;
        k-=sum;
        t[p]--;
        return ;
    }
    if((k>sum+t[2*p+1]-1+invmax(t[0]-1))||(t[2*p+1]==0)){
        sum+=t[2*p+1];
        update(2*p+2, m+1, dr, sum);
    }else{
        update(2*p+1, st, m, sum);
    }
    t[p]=t[2*p+1]+t[2*p+2];
}
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;
    FILE *fin, *fout;
    fin=fopen("farfurii.in", "r");
    fout=fopen("farfurii.out", "w");
    fscanf(fin, "%d%lld", &n, &k);
    dfs(0, 0, n-1);
    for(i=0; i<n-1; i++){
        update(0, 0, n-1, 0);
        fprintf(fout, "%d ", ans+1);
    }
    update(0, 0, n-1, 0);
    fprintf(fout, "%d\n", ans+1);
    fclose(fin);
    fclose(fout);
    return 0;
}