Cod sursa(job #2974783)

Utilizator alin_simpluAlin Pop alin_simplu Data 4 februarie 2023 17:22:13
Problema Farfurii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <vector>
using namespace std;

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

vector<int> arb;
int N, K;

void Build(int node, int left, int right)
{
    if (left == right)
    {
        arb[node] = 1;
        return;
    }

    auto mid = (left + right) >> 1;
    Build((node << 1), left, mid);
    Build((node << 1) + 1, mid + 1, right);

    arb[node] = arb[(node << 1)] + arb[(node << 1) + 1];
}

void Update(int node, int left, int right, int pos)
    {
        if (left == right)
        {
            arb[node] = 0;
            fout << left << '\n';
        }
        else
        {
            auto mid = (left + right) >> 1;
            if (pos <= arb[node * 2])
            Update(node * 2, left, mid, pos);

            else
            Update(node * 2 + 1, mid + 1, right, pos - arb[node * 2]);
            arb[node] = arb[node<<1|1] + arb[node<<1];
        }
    }


int main()
{
    fin >> N >> K;
    arb.resize(4 * N);
    Build(1, 1, N);

    for (int i = 1; i <= N; ++i) {
        if (K <= (N - i) * (N - i - 1) / 2)
            Update(1, 1, N, 1);
        else
        {
            Update(1, 1, N, 1 + K - (N - i) * (N - i - 1) / 2);
            K = (N - i) * (N - i - 1) / 2;
        }

    }
    return 0;
}