Cod sursa(job #3288772)

Utilizator amunnumeVlad Patrascu amunnume Data 24 martie 2025 11:13:57
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
const int N=1e5+5;
struct aib
{
    int n,v[N];
    void init(int n)
    {
        for(int i=1;i<=n;++i)
        {
            v[i]=(i&-i);
        }
    }
    void update(int p,int val)
    {
        for(int i=p;i<=n;i+=(i&-i))
        {
            v[i]+=val;
        }
    }
    int query(int p)
    {
        int t=0;
        if(!p) return 0;
        for(int i=p;i;i-=(i&-i))
        {
            t+=v[i];
        }
        return t;
    }
    int bin(int val)
    {
        int st=1,dr=n,sol=0,mid;
        while(st<=dr)
        {
            mid=(st+dr)>>1;
            if(query(mid-1)>val)
            {
                dr=mid-1;
            }
            else
            {
                sol=mid;
                st=mid+1;
            }
        }
        return sol;
    }
};
int n,i,j,r,sol[N];
long long k,f[N];
aib a;
void print()
{
    for(i=1;i<=n;++i)
    {
        fout<<sol[i]<<' ';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    fin>>n>>k;
    a.n=n;
    a.init(n);
    for(i=1;i<=n;++i)
    {
        f[i]=(1ll*i*(i-1)/2);
    }
    for(i=1;i<=n;++i)
    {
        if(f[n-i]>=k)
        {
            r=i;
            sol[i]=i;
            a.update(i,-1);
        }
        else
        {
            break;
        }
    }
    for(i=r+1;i<=n;++i)
    {
        int lim=k-f[n-i];
        int x=a.bin(lim);
        k-=a.query(x-1);
        a.update(x,-1);
        sol[i]=x;
    }
    print();
    return 0;
}