Cod sursa(job #2282243)

Utilizator I_am_not_a_robotMr Domino I_am_not_a_robot Data 13 noiembrie 2018 15:20:59
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>

using namespace std;

ifstream fin("farfurii.in");
ofstream fout("farfurii.out");


typedef long long ll;

const int N=100000+5;

int n;
ll cnt;

int v[N];

int aib[N];

inline void add(int p,int x)
{
    for(int i=p;i<=n;i+=i&(-i))
    {
        aib[i]+=x;
    }
}

int main()
{
    fin>>n>>cnt;
    for(int i=1;i<=n;i++)
    {
        ll lft=n-i;
        ll x=lft*(lft-1)/2;
        if(cnt<=x)
        {
            v[i]=0;
        }
        else
        {
            v[i]=cnt-x;
        }
        cnt-=v[i];
    }
    for(int i=1;i<=n;i++)
    {
        v[i]++;
        int r=0,pas=(1<<16);
        int now=0;
        while(pas)
        {
            if(r+pas<=n)
            {
                int id=r+pas;
                if(id+now+aib[id]<v[i])
                {
                    r+=pas;
                    now+=aib[id];
                }
            }
            pas/=2;
        }
        r++;
        add(r,-1);
        fout<<r<<" ";
    }
    fout<<"\n";
    return 0;
}