Cod sursa(job #3241813)

Utilizator Anul2024Anul2024 Anul2024 Data 4 septembrie 2024 12:45:06
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
using namespace std;
ifstream fin ("farfurii.in");
ofstream fout ("farfurii.out");
int v,n,m,i,aib[100001];
long long val,k;
void update (int i,int val)
{
    for (; i<=n; i+=(i&-i))
        aib[i]+=val;
}
int query_poz (int val)
{
    int poz=0,sum=0;
    for (int bit=16; bit>=0; bit--)
    {
        if (poz+(1<<bit)<=n&&sum+aib[poz+(1<<bit)]<val)
        {
            sum+=aib[poz+(1<<bit)];
            poz+=(1<<bit);
        }
    }
    return poz+1;
}
int main ()
{
    fin>>n>>k;
    for (i=1; i<=n; i++)
        update (i,1);
    for (i=1; i<=n; i++)
    {
        m=n-i;
        val=1ll*m*(m-1)/2;
        if (val>=k&&k>0)
            v=query_poz (1);
        else if (k==0)
            v=query_poz (m+1);
        else
        {
            v=query_poz (k-val+1);
            k=0;
        }
        update (v,-1);
        fout<<v<<" ";
    }
    return 0;
}