Cod sursa(job #1825818)

Utilizator aaether14Dinescu Stefan Cristian aaether14 Data 9 decembrie 2016 18:33:34
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <algorithm>
#include <stdint.h>


int64_t n, k;
int64_t tree[400004];




void modify(int64_t node, int64_t left, int64_t right, int64_t position, int64_t value)
{

        if (left==right)
        {
                tree[node] = value;
                return;
        }
        int64_t middle = (left+right)>>1;
        if (position <= middle)
                modify(node<<1, left, middle, position, value);
        else
                modify(node<<1|1, middle+1, right, position, value);
        tree[node] = tree[node<<1] + tree[node<<1|1];

}



int64_t query(int64_t node, int64_t left, int64_t right, int64_t value)
{
        if (left==right) return left;
        int64_t middle = (left+right)>>1;
        if (value <= tree[node<<1])
                return query(node<<1, left, middle, value);
        else
                return query(node<<1|1, middle+1, right, value-tree[node<<1]);
}


int main()
{


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


        fin>>n>>k;
        for (int64_t i = 1; i <= n; ++i)
                modify(1, 1, n, i, 1);


        for (int64_t i = n; i > 0; --i)
        {
                int64_t needed_inversions = std::max(int64_t(0), k-(i-1)*(i-2)/2);
                k = std::max(int64_t(0), k-needed_inversions); 
                int64_t place = query(1, 1, n, needed_inversions+1);
                fout<<place<<" ";
                modify(1, 1, n, place, 0);
        }


        fin.close();
        fout.close();
        return 0;


}