Cod sursa(job #2737491)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 4 aprilie 2021 19:53:07
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <iostream>

using namespace std;

long long put=1;
int aint[400005];

void update(long long poz)
{
    while(poz>1)
    {
        aint[poz]=aint[2*poz]+aint[2*poz+1];
        poz/=2;
    }
}
int query(long long val)
{
    int poz=1,aux=0;
    while(poz<put)
    {
        if(aint[2*poz]+aux<val)
        {
            aux+=aint[2*poz];
            poz*=2;
            poz++;
        }
        else
        {
            poz*=2;
        }
    }
    return poz-put+1;
}

int main()
{
    ifstream cin ("farfurii.in");
    ofstream cout ("farfurii.out");
    long long k,n;
    cin>>n>>k;
    while(put<n)
        put<<=1;
    for(int i=1; i<=n; i++)
    {
        aint[i+put-1]=1;
        update((i+put-1)/2);
    }
    long long temp,last,aux;
    for (int i= 1; i <= n; ++i)
    {
        temp=(n-i)*(n-i-1)/2;
        if(temp>=k)
        {
            last=0;
        }
        else
        {
            last=k-temp;
        }
        k-=last;
        aux=query(last+1);
        cout<<aux<<" ";
        aint[aux+put-1]=0;
        update((aux+put-1)/2);
    }
    return 0;
}