Cod sursa(job #2310178)

Utilizator lucianistratiIstrati Lucian lucianistrati Data 30 decembrie 2018 18:25:32
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <iostream>
#define si(nr) (nr&(-nr))
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
long long s,x;
int v[100001],aib[100001],i,N,K,r,pas,aux,index;
void adaugare(int p,int x)
{
    int i;
    for(i=p;i<=N;i+=si(i))
    {
        aib[i]+=x;
    }
}
void construire_v()
{
    fin>>N>>K;
    for(i=1;i<=N;i++)
    {
        s=N-i;
        x=(s*(s-1))/2;
        if(K>x)
        {
            v[i]=K-x;
        }
        else
        {
            v[i]=0;
        }
        K-=v[i];
    }
}
int f(int r)
{
    pas=(1<<16);
    aux=0;
    while(pas!=0)
    {
        if(r+pas<=N)
        {
            index=r+pas;
            if(index+aux+aib[index]<v[i])
            {
                r+=pas;
                aux+=aib[index];
            }
        }
        pas/=2;
    }
    return r;
}
int main()
{
    construire_v();
    for(i=1;i<=N;i++)
    {
        v[i]++;
        r=f(0);
        r++;
        adaugare(r,-1);
        fout<<r<<" ";
    }
    fin.close();
    fout.close();
    return 0;
}