Pagini recente » Cod sursa (job #1325647) | Cod sursa (job #2088149) | Cod sursa (job #2985865) | Cod sursa (job #2082185) | Cod sursa (job #1779860)
#include <fstream>
#include <vector>
using namespace std;
inline int PutereZerouri(int x)
{
return (x & (x - 1)) ^ x;
}
void Adauga(vector<long long> &aib, unsigned poz, int val)
{
while (poz < aib.size()) {
aib[poz] += 1LL * val;
poz += PutereZerouri(poz);
}
}
long long AflaSuma(const vector<long long> &aib, int poz)
{
long long suma = 0;
while (poz > 0) {
suma += aib[poz];
poz -= PutereZerouri(poz);
}
return suma;
}
int Gaseste(const vector<long long> &aib, int k)
{
unsigned poz = 0;
unsigned put = (1 << 31);
while (put > 0) {
if (poz + put < aib.size() && AflaSuma(aib, poz + put) < 1LL * k)
poz += put;
put >>= 1;
}
return poz + 1;
}
int main()
{
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
long long n, k;
fin >> n >> k;
if (k == n * (n - 1) / 2) {
while (n--)
fout << n + 1 << " ";
return 0;
}
vector<long long> aib(n + 1, 0);
for (int i = 1; i <= n; ++i)
Adauga(aib, i, 1);
int len = n - 1;
for (int i = 1; i <= n; ++i) {
int ordin = max(1, int(k - len * (len - 1) / 2 + 1));
k -= (ordin - 1);
int poz = Gaseste(aib, ordin);
Adauga(aib, poz, -1);
fout << poz << " ";
--len;
}
return 0;
}