Cod sursa(job #3288952)

Utilizator Victor5539Tanase Victor Victor5539 Data 24 martie 2025 22:08:22
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <fstream>
#define int long long
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");

const int MAX=1e5;
int n,k,maxim[MAX+5],A[4*MAX+5],i,s[MAX+5],v[MAX+5],st,dr,mij,sol[MAX+5],poz;

void build(int nod, int st ,int dr)
{
    if (st==dr)
        A[nod]=1;
    else
    {
        int mij=(st+dr)>>1;
        build(2*nod,st,mij);
        build(2*nod+1,mij+1,dr);
        A[nod]=A[2*nod]+A[2*nod+1];
    }
}

void update(int nod, int st ,int dr ,int p)
{
    if (st==dr)
        A[nod]=0;
    else
    {
        int mij=(st+dr)>>1;

        if (p<=mij)
            update(2*nod,st,mij,p);
        else
            update(2*nod+1,mij+1,dr,p);

        A[nod]=A[2*nod]+A[2*nod+1];
    }
}

void getpoz(int nod, int st ,int dr ,int k)
{
    if (st==dr)
        poz=st;
    else
    {
        int mij=(st+dr)>>1;

        if (A[2*nod]>=k)
            getpoz(2*nod,st,mij,k);
        else
            getpoz(2*nod+1,mij+1,dr,k-A[2*nod]);
    }
}

signed main()
{
    fin>>n>>k;

    for (i=1; i<=n; i++)
        maxim[i]=n-i;

    for (i=n; i>=1; i--)
        s[i]=s[i+1]+maxim[i];

    for (i=1; i<=n; i++)
    {
        poz=0;
        st=0; dr=maxim[i];

        while (st<=dr)
        {
            mij=(st+dr)>>1;

            if (mij+s[i+1]>=k)
            {
                poz=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }


        v[i]=poz;
        k-=poz;
    }

    build(1,1,n);

    for (i=1; i<=n; i++)
    {
        poz=0;
        getpoz(1,1,n,v[i]+1);
        sol[i]=poz;
        update(1,1,n,poz);
    }

    for (i=1; i<=n; i++)
        fout<<sol[i]<<" ";







    return 0;
}