Cod sursa(job #2442844)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 25 iulie 2019 14:34:53
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>

using namespace std;

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

const int NMAX = 1e5 + 5;

int N, A[NMAX], AIB[NMAX];

long long K;

static inline int UB (int X)
{
    return (X & (-X));
}

static inline void Update (int pos, int val)
{
    for(int i = pos; i <= N; i += UB(i))
        AIB[i] += val;
}

static inline int Query (int pos)
{
    int sum = 0;

    for(int i = pos; i >= 1; i -= UB(i))
        sum += AIB[i];

    return sum;
}

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(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(i, 1);

    for(int i = 1; i <= N; ++i)
    {
        long long Max = Maxim_Inv(i + 1, N);

        if(K <= Max)
            A[i] = CB(1);
        else
        {
            int Diff = (int)(K - Max);

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

            K -= 1LL * Diff;
        }

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

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

    g << '\n';

    return 0;
}