Cod sursa(job #2066382)

Utilizator leraValeria lera Data 14 noiembrie 2017 22:41:49
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#define Nmax 100005

using namespace std;

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

int arb[4 * Nmax], n, k;

void upd(int nod, int L, int R, int valp)
{
    int mij = (L + R) / 2;
    if(L == R)
    {
        arb[nod] = 1;
        fout << L << ' ';
        return;
    }
    if(valp <= (mij - L + 1) - arb[2 * nod])
        upd(2 * nod, L, mij, valp);
    else
        upd(2 * nod + 1, mij + 1, R, valp - ((mij - L + 1) - arb[2 * nod]));
    arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
}
int main()
{
    fin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        if( k <= (n - i) * (n - i - 1) / 2)//pun cel mai mic nr disponibil
        {
            upd(1, 1, n, 1);
        }
        else
        {
            int aux = k - (n - i) * (n - i - 1) /2;
            k = (n - i) * (n - i - 1) /2;
            upd(1, 1, n, aux + 1);// a k a valoare disponibila
        }
       // for(int j = 1; j <= 13; j++)fout << arb[j] <<" " ;
        //fout << '\n';
    }
    return 0;
}