Cod sursa(job #2616079)

Utilizator As932Stanciu Andreea As932 Data 16 mai 2020 16:40:44
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>

using namespace std;

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

const int nmax=100005;

int n,k,nr,rem;
int aib[nmax],ans[nmax];

void update(int poz,int val)
{
    for(;poz<=n;poz+= poz & -poz)
        aib[poz]+=val;
}

int query(int poz)
{
    int s=0;

    for(;poz>0;poz-= poz & -poz)
        s+=aib[poz];
    return s;
}

int bin(int val)
{
    int st=1,dr=n,r=0;

    while(st<=dr)
    {
        int mij=(st+dr)/2;

        if(query(mij)<val)
            st=mij+1;
        else
        {
            r=mij;
            dr=mij-1;
        }
    }

    return r;
}

int main()
{
    cin>>n>>k;

    for(int i=1;i<=n;i++)
        update(i,1);

    for(int i=1;i<=n;i++)
    {
        nr=1;

        long long inv=1LL*(n-i)*(n-i-1)/2;

        if(inv<k)
        {
            rem=k-inv;
            nr=rem+1;
            k-=1LL*rem;
        }

        ans[i]=bin(nr);

        update(ans[i],-1);
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";

    return 0;
}