Cod sursa(job #1828588)

Utilizator preda.andreiPreda Andrei preda.andrei Data 13 decembrie 2016 16:56:28
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <vector>

using namespace std;

inline int PutereZerouri(int n)
{
    return n & (n ^ (n - 1));
}

void Adauga(vector<int> &aib, int poz, int val)
{
    while (poz < aib.size()) {
        aib[poz] += val;
        poz += PutereZerouri(poz);
    }
}

int Suma(const vector<int> &aib, int poz)
{
    int suma = 0;
    while (poz > 0) {
        suma += aib[poz];
        poz -= PutereZerouri(poz);
    }
    return suma;
}

int KElement(const vector<int> &aib, int k)
{
    int put = (1 << 25);
    int poz = 0;

    while (put > 0) {
        if (poz + put < aib.size() && Suma(aib, poz + put) < k)
            poz += put;
        put >>= 1;
    }
    return poz + 1;
}

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

    int n, m;
    fin >> n >> m;

    vector<int> aib(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        Adauga(aib, i, 1);

    for (int i = 1; i <= n; ++i) {
        int ramas = n - i + 1;
        int elem_urmator = 0;

        if (1LL * (ramas - 1) * (ramas - 2) / 2 >= m) {
            elem_urmator = KElement(aib, 1);
        } else {
            int k = 2;
            while (k < ramas && m > (ramas - 1) * (ramas - 2) / 2 + k - 1)
                ++k;
            m -= (k - 1);
            elem_urmator = KElement(aib, k);
        }

        fout << elem_urmator << " ";
        Adauga(aib, elem_urmator, -1);
    }

    return 0;
}