Cod sursa(job #2614567)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 11 mai 2020 22:07:00
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>

using namespace std;

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

using ll = long long;

const int NMAX = 1e5 + 5;

int N;
ll K;

int A[NMAX];

class FenwickTree
{
    int A[NMAX];

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

    inline int Query (int pos)
    {
        int r = 0;

        for(int i = pos; i >= 1; i -= UB(i))
            r += A[i];

        return r;
    }

public:
    inline void Update (int pos, int Val)
    {
        for(int i = pos; i <= N; i += UB(i))
            A[i] += Val;

        return;
    }

    inline int Find_the_n_th_Active (int n)
    {
        int Left = 1, Right = N, ans = N;

        while(Left <= Right)
        {
            int Mid = (Left + Right) >> 1;

            if(Query(Mid) >= n)
            {
                ans = Mid;

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

        return ans;
    }
} AIB;

static inline void Read ()
{
    f.tie(nullptr);

    f >> N >> K;

    return;
}

static inline void Initialize (int N)
{
    for(int i = 1; i <= N; ++i)
        AIB.Update(i, 1);

    return;
}

static inline ll Count (int Left, int Right)
{
    int Lg = (Right - Left + 1);

    return (1LL * (1LL * Lg * (1LL * Lg - 1LL)) >> 1LL);
}

static inline void Solve ()
{
    Initialize(N);

    for(int i = 1; i <= N; ++i)
    {
        ll Maximum_Remaining = Count(i + 1, N);
        int Id = 1;

        if(Maximum_Remaining < K)
        {
            int Delta = K - Maximum_Remaining;

            Id = Delta + 1;

            K -= 1LL * Delta;
        }

        A[i] = AIB.Find_the_n_th_Active(Id);
        AIB.Update(A[i], -1);
    }

    return;
}

static inline void Write ()
{
    for(int i = 1; i <= N; ++i)
    {
        g << A[i];

        if(i != N)
            g << ' ';
    }

    g << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    Write();

    return 0;
}