Cod sursa(job #1779860)

Utilizator preda.andreiPreda Andrei preda.andrei Data 15 octombrie 2016 17:30:31
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <vector>

using namespace std;

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

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

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

int Gaseste(const vector<long long> &aib, int k)
{
    unsigned poz = 0;
    unsigned put = (1 << 31);

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

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

    long long n, k;
    fin >> n >> k;

    if (k == n * (n - 1) / 2) {
    	while (n--)
    		fout << n + 1 << " ";
    	return 0;
    }

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

    int len = n - 1;
    for (int i = 1; i <= n; ++i) {
        int ordin = max(1, int(k - len * (len - 1) / 2 + 1));
        k -= (ordin - 1);

        int poz = Gaseste(aib, ordin);
        Adauga(aib, poz, -1);
        fout << poz << " ";
        --len;
    }

    return 0;
}