Cod sursa(job #2065654)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 13 noiembrie 2017 23:37:36
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
const int Nmax = 100000 + 5;
int n, k, arb[4 * Nmax];
void update(int nod, int l, int r, int poz, int val)
{
    int mid = l + (r - l)/ 2;

    if(l == r)
    {
        arb[nod] += val;
        return;
    }
    if(poz <= mid)update(2 *nod, l, mid, poz, val);
    else update(2 *nod + 1, mid + 1, r, poz, val);
    arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
}
int query(int nod, int l, int r, int val)
{
    int mid = l + (r - l)/ 2;

    if(l == r)return l;
    if(val <= arb[2 * nod])
        return query(2 * nod, l, mid, val);
    val -= arb[2 * nod];
    return query(2 * nod + 1, mid + 1, r, val);

}
int main()
{
    fin >> n >> k;
    for(int i = 1; i <= n; ++i)
        update(1, 1, n, i, 1);
    for(int i = n; i >= 1; --i)
    {
        if(k <= 1LL  * (i - 1) * (i - 2) / 2)
        {
            int poz = query(1, 1, n, 1);
            update(1, 1 , n, poz, -1);
            fout << poz << ' ';
        }
        else
        {
            int aux = k -1LL * (i - 1) * (i - 2) / 2;
            k -= aux;
            int poz = query(1, 1, n, aux + 1);
            update(1, 1, n, poz, -1);
            fout << poz << ' ';
        }
    }
    return 0;
}