Pagini recente » Cod sursa (job #715718) | Cod sursa (job #1687699) | Cod sursa (job #2021423) | Cod sursa (job #1782971) | Cod sursa (job #3157112)
#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;
}