Cod sursa(job #1828606)

Utilizator preda.andreiPreda Andrei preda.andrei Data 13 decembrie 2016 17:20:36
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <vector>

using namespace std;

using int64 = long long;

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

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

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

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

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

inline int64 NrMaxInversiuni(int64 n)
{
    return n * (n - 1) / 2;
}

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

    int64 n, m;
    fin >> n >> m;

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

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

        if (NrMaxInversiuni(ramas - 1) >= m) {
            elem_urmator = KElement(aib, 1);
        } else {
            int poz = 0;
            int put = (1 << 25);
            while (put > 0) {
                int poz_nou = poz + put;
                if (poz_nou <= ramas && NrMaxInversiuni(ramas - 1) + poz_nou - 1 < m)
                    poz = poz_nou;
                put >>= 1;
            }
            m -= poz;
            elem_urmator = KElement(aib, poz + 1);
        }

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

    return 0;
}