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