Cod sursa(job #1038211)

Utilizator teoionescuIonescu Teodor teoionescu Data 21 noiembrie 2013 10:39:32
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream>
using namespace std;
ifstream in("farfurii.in");
ofstream out("farfurii.out");
const int Nmax = 100000;
long long N,K,ch[Nmax];
long long A[18*Nmax];
void Build(int st,int dr,int i){
    A[i]=dr-st+1;
    if(st!=dr){
        int mij=(st+dr)/2;
        Build(st,mij,2*i);
        Build(mij+1,dr,2*i+1);
    }
}
int Query(int val,int st,int dr,int i){
    if(st==dr) return st;
    int mij=(st+dr)/2;
    if( val <= A[2*i]) return Query(val,st,mij,2*i);
    return Query(val-A[2*i],mij+1,dr,2*i+1);
}
void Update(int wh,int st,int dr,int i){
    A[i]--;
    if(st!=dr){
        int mij=(st+dr)/2;
        if( wh <= mij) Update(wh,st,mij,2*i);
        else Update(wh,mij+1,dr,2*i+1);
    }
}
int Detect(int i){
    int ind = Query(i,1,N,1);
    Update(ind,1,N,1);
    return ind;
}
int main(){
    in>>N>>K;
    for(int i=1;i<=N;i++) ch[N-i+1]=i-1;
    for(int i=N;i>=1;i--){
        if( K-ch[i] >= 0 ) K-=ch[i];
        else{
            ch[i]=K;
            K=0;
        }
    }
    for(int i=1;i<=N;i++) ch[i]++;
    Build(1,N,1);
    for(int i=1;i<=N;i++){
        out<<Detect(ch[i])<<' ';
    }
    return 0;
}