Pagini recente » Cod sursa (job #427644) | Cod sursa (job #1706555) | Cod sursa (job #1332183) | Istoria paginii runda/concursulalablanao/clasament | Cod sursa (job #1828606)
#include <fstream>
#include <vector>
using namespace std;
using int64 = long long;
inline int PutereZerouri(int n)
{
return n & (n ^ (n - 1));
}
void Adauga(vector<int64> &aib, int poz, int64 val)
{
while (poz < aib.size()) {
aib[poz] += val;
poz += PutereZerouri(poz);
}
}
int64 Suma(const vector<int64> &aib, int poz)
{
int64 suma = 0;
while (poz > 0) {
suma += aib[poz];
poz -= PutereZerouri(poz);
}
return suma;
}
int KElement(const vector<int64> &aib, int64 k)
{
int64 put = (1 << 25);
int64 poz = 0;
while (put > 0) {
if (poz + put < aib.size() && Suma(aib, poz + put) < k)
poz += put;
put >>= 1;
}
return poz + 1;
}
inline int64 NrMaxInversiuni(int64 n)
{
return n * (n - 1) / 2;
}
int main()
{
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
int64 n, m;
fin >> n >> m;
vector<int64> aib(n + 1, 0);
for (int i = 1; i <= n; ++i)
Adauga(aib, i, 1);
for (int i = 1; i <= n; ++i) {
int64 ramas = n - i + 1;
int64 elem_urmator = 0;
if (NrMaxInversiuni(ramas - 1) >= m) {
elem_urmator = KElement(aib, 1);
} else {
int poz = 0;
int put = (1 << 25);
while (put > 0) {
int poz_nou = poz + put;
if (poz_nou <= ramas && NrMaxInversiuni(ramas - 1) + poz_nou - 1 < m)
poz = poz_nou;
put >>= 1;
}
m -= poz;
elem_urmator = KElement(aib, poz + 1);
}
fout << elem_urmator << " ";
Adauga(aib, elem_urmator, -1);
}
return 0;
}