Cod sursa(job #3157112)

Utilizator SSKMFSS KMF SSKMF Data 14 octombrie 2023 13:23:41
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
using namespace std;

ifstream cin ("farfurii.in");
ofstream cout ("farfurii.out");

int suma[100001];

int main ()
{
    int lungime , inversiuni;
    cin >> lungime >> inversiuni;

    auto Suma = [&] (int indice) -> int 
        { int total = 0; while (indice) { total += suma[indice]; indice -= (indice & -indice); } return total; };

    auto Update = [&] (int indice) -> void
        { while (indice <= lungime) { suma[indice]++; indice += (indice & -indice); } };

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        int stanga = 1 , dreapta = lungime - indice + 1 , ramas = 1;
        const long long maxim = 1LL * (lungime - indice) * (lungime - indice - 1) / 2;
        while (stanga <= dreapta)
        {
            const int mijloc = (stanga + dreapta) >> 1;
            if (maxim + mijloc - 1 >= inversiuni)
                { dreapta = mijloc - 1; ramas = mijloc; }
            else
                stanga = mijloc + 1;
        }
        
        int salt = (1 << 16) , valoare = 0;
        while (salt)
        {
            if (salt + valoare <= lungime && salt + valoare - Suma(salt + valoare) < ramas)
                valoare += salt;
            
            salt >>= 1;
        }

        inversiuni -= ramas - 1;
        cout << ++valoare << ' ';
        Update(valoare);
    }

    cout.close(); cin.close();
    return 0;
}