Cod sursa(job #1213510)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 28 iulie 2014 12:53:04
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
/*#include<cstdio>
const int N=100000;
int n;
class Bit{
    public:
        int v[N+1];
        int query(int p){
            int res;
            while(p>0){
                res+=this->v[p];
                p-=p&-p;
            }
            return res;
        }
        void update(int p){
            while(p<=n){
                this->v[p]++;
                p+=p&-p;
            }
        }
};
Bit bit;
bool vis[N+1];
FILE*in,*out;
int min1,min2,max1,max2,p,k;
void scan(){
    fscanf(in,"%d%d",&n,&k);
}
void init(){
    in=fopen("farfurii.in","r");
    out=fopen("farfurii.out","w");
    scan();
}
void bsearch(){
    int l=1,r=n,m;
    while(l<r-1){
        m=(l+r)/2;
        if(vis[m])
            continue;
        min2=min1+m-1-bit.query(m-1);
        max2=min2+(n-m)*(n-m-1)/2;
        if(k>=min2)
            r=m;
        else
            l=m;
    }
    min2=min1+l-1-bit.query(l-1);
    max2=min2+(n-l)*(n-l-1)/2;
    if(min2<=k&&max2<=k)
        p=l;
    else
        p=r;
}
void solve(){
    int i;
    for(i=1;i<=n;i++){
        bsearch();
        bit.update(p);
        fprintf(out,"%d ",p);
        vis[p]=true;
    }
}
int main(){
    init();
    solve();
    return 0;
}*/
#include<cstdio>
const int N=100000;
bool vis[N+1];
FILE*in,*out;
int n,k;
void scan(){
    fscanf(in,"%d%d",&n,&k);
}
void init(){
    in=fopen("farfurii.in","r");
    out=fopen("farfurii.out","w");
    scan();
}
void solve(){
    int i,x=n,nr;
    for(i=1;i<=n;i++){
        nr=(x-1)*(x-2)/2;
        if(k>=nr)
            break;
        x--;
        vis[i]=true;
        fprintf(out,"%d ",i);
    }
    if(k-nr+i>0)
        fprintf(out,"%d ",k-nr+i);
        vis[k-nr+i]=true;
    for(i=n;i>=1;i--)
        if(!vis[i])
            fprintf(out,"%d ",i);
}
int main(){
    init();
    solve();
    return 0;
}