Cod sursa(job #2442843)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 25 iulie 2019 14:31:17
Problema Farfurii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>

using namespace std;

ifstream f("farfurii.in");
ofstream g("farfurii.out");

const int NMAX = 1e5 + 5;

int N, A[NMAX], V[4 * NMAX];

long long K;

static inline void Update (int Node, int a, int b, int pos, int val)
{
    if(a == b)
    {
        V[Node] += val;

        return;
    }

    int Mid = (a + b) / 2;

    if(pos <= Mid)
        Update(2 * Node, a, Mid, pos, val);

    if(pos > Mid)
        Update(2 * Node + 1, Mid + 1, b, pos, val);

    V[Node] = V[2 * Node] + V[2 * Node + 1];

    return;
}

static inline int Query (int Node, int a, int b, int qa, int qb)
{
    if(qa <= a && b <= qb)
        return V[Node];

    int p1 = 0, p2 = 0;

    int Mid = (a + b) / 2;

    if(qa <= Mid)
        p1 = Query(2 * Node, a, Mid, qa, qb);

    if(qb > Mid)
        p2 = Query(2 * Node + 1, Mid + 1, b, qa, qb);

    return (p1 + p2);
}

static inline long long Maxim_Inv (int Left, int Right)
{
    int Lg = (Right - Left + 1);

    return 1LL * (1LL * Lg * 1LL * (Lg - 1)) / (1LL * 2);
}

static inline int CB (int X)
{
    int Left = 1, Right = N, pos = 0;

    while(Left <= Right)
    {
        int Mid = (Left + Right) / 2;

        if(Query(1, 1, N, 1, Mid) >= X)
        {
            pos = Mid;

            Right = Mid - 1;
        }
        else
            Left = Mid + 1;
    }

    return pos;
}

int main()
{
    f.tie(NULL);

    f >> N >> K;

    for(int i = 1; i <= N; ++i)
        Update(1, 1, N, i, 1);

    for(int i = 1; i <= N; ++i)
    {
        if(K <= Maxim_Inv(i + 1, N))
            A[i] = CB(1);
        else
        {
            int Diff = (int)(K - Maxim_Inv(i + 1, N));

            A[i] = CB(Diff + 1);

            K -= 1LL * Diff;
        }

        Update(1, 1, N, A[i], -1);
    }

    for(int i = 1; i <= N; ++i)
        g << A[i] << ' ';

    g << '\n';

    return 0;
}