Cod sursa(job #1779873)

Utilizator preda.andreiPreda Andrei preda.andrei Data 15 octombrie 2016 17:38:40
Problema Farfurii Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <vector>

#include <iostream>

using namespace std;

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

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

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

long long  Gaseste(const vector<long long> &aib, long long  k)
{
    long long poz = 0;
    long long put = (1LL << 61);

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

int main()
{
    FILE *fin = fopen("farfurii.in", "r");
    FILE *fout = fopen("farfurii.out", "w");

    long long n, k;
    fscanf(fin, "%lld%lld", &n, &k);

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

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

        long long  poz = Gaseste(aib, ordin);
        Adauga(aib, poz, -(1LL));
        fprintf(fout, "%lld ", poz);
        cout << poz << "\n";
        cout.flush();
        --len;
    }

    return 0;
}