Pagini recente » Cod sursa (job #1682946) | Cod sursa (job #1193886) | Cod sursa (job #1832353) | Cod sursa (job #1509416) | Cod sursa (job #2649271)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("farfurii.in");
ofstream fo("farfurii.out");
typedef long long ll;
const int NMAX = 1e5 + 5;
int n, k;
ll aib[NMAX];
bool luat[NMAX];
inline int lsb(int x) {
return x & (-x);
}
void update(int poz, int val) {
for (; poz <= n; poz += lsb(poz))
aib[poz] += val;
}
ll query(int poz) {
ll ret = 0;
for (; poz; poz -= lsb(poz))
ret += aib[poz];
return ret;
}
int main()
{
fi >> n >> k;
for (int i = 1; i <= n; i++) {
update(i, i - 1);
update(i + 1, -(i - 1));
}
ll curr = 0;
for (int i = 1; i <= n; i++) {
// primul x a.i. maiMic(X) >= k-curr-(n-i-1)(n-i)/2
ll ceva = k - curr - 1LL * (n - i - 1) * (n - i) / 2;
int st = 1;
for (int b = 16; b >= 0; b--) {
if (st + (1 << b) <= n && query(st + (1 << b)) < ceva)
st += (1 << b);
}
if (query(st) < ceva)
st++;
while (luat[st]) //eh...
st++;
update(st + 1, -1);
fo << st << " ";
curr += query(st);
luat[st] = 1;
}
return 0;
}