Pagini recente » Monitorul de evaluare | Cod sursa (job #416551) | Cod sursa (job #1046301) | Cod sursa (job #1830326) | Cod sursa (job #1779834)
#include <fstream>
#include <vector>
using namespace std;
inline long long PutereZerouri(long long x)
{
return (x & (x - 1)) ^ x;
}
void Adauga(vector<long long> &aib, unsigned poz, long long val)
{
while (poz < aib.size()) {
aib[poz] += val;
poz += PutereZerouri(poz);
}
}
long long AflaSuma(const vector<long long> &aib, long long poz)
{
long long suma = 0;
while (poz > 0) {
suma += aib[poz];
poz -= PutereZerouri(poz);
}
return suma;
}
long long Gaseste(const vector<long long> &aib, long long k)
{
unsigned poz = 0;
unsigned put = (1 << 31);
while (put > 0) {
if (poz + put < aib.size() && AflaSuma(aib, poz + put) < 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 (long long i = 1; i <= n; ++i)
Adauga(aib, i, 1);
long long len = n - 1;
for (long long i = 1; i <= n; ++i) {
long long ordin = max(1LL, k - len * (len - 1) / 2 + 1);
k -= (ordin - 1);
long long poz = Gaseste(aib, ordin);
Adauga(aib, poz, -1);
fout << poz << " ";
--len;
}
return 0;
}