Cod sursa(job #1327120)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 26 ianuarie 2015 13:24:37
Problema Farfurii Scor 100
Compilator cpp Status done
Runda simulareoji2015 Marime 1.26 kb
#include <fstream>

#define NMAX 100000
#define lsb(x) ((x)&(-x))
using namespace std;

int n;
int aib[NMAX+5];

inline void update (int x) {
    for(int i=x;i<=n;i+=lsb(i))
        aib[i]--;
}

inline int sum (int x) {
    int s=0;
    for(;x;x-=lsb(x))
        s+=aib[x];

    return s;
}

inline int xth (int x) {
    int st=1;
    int dr=n;
    int mijl=(n+1)/2;
    int minim=n;

    while(st<=dr) {
        if(sum(mijl)>=x) {
            if(mijl<minim)
                minim=mijl;
            dr=mijl-1;
        }
        else
            st=mijl+1;

        mijl=(st+dr)>>1;
    }

    return minim;
}

int main()
{
    ifstream cin("farfurii.in");
    ofstream cout("farfurii.out");

    long long int k=0;
    cin>>n>>k;

    long long int x;
    int numarul;

    for(int i=1;i<=n;i++)
        aib[i]=lsb(i);

    for(int i=1;i<=n;i++) {
        x=((n-i)*(n-i-1ll))/2;

        if(k+1<=x) {
            numarul=xth(1);
            update(numarul);
            cout<<numarul<<' ';
        }
        else {
            numarul=xth(k+1-x);
            update(numarul);
            cout<<numarul<<' ';
            k=x;
        }
    }
    cout<<'\n';

    cin.close();
    cout.close();
    return 0;
}