Pagini recente » Cod sursa (job #2914123) | Cod sursa (job #1123998) | Cod sursa (job #2867570) | Cod sursa (job #2158305) | Cod sursa (job #1361924)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("farfurii.in");
ofstream out("farfurii.out");
const int Nmax = 100005;
const int tree_size = 262144;
typedef long long int64;
int n;
int64 k;
int tree[tree_size];
int taken[Nmax];
int position, result, a, b;
void update(int node, int l, int r) {
if (l == r)
tree[node] = 0;
else {
int m = (l + r) >> 1;
if (position <= m) update(node << 1, l, m);
else update((node << 1) + 1, m + 1, r);
tree[node] = tree[node << 1] + tree[(node << 1) + 1];
}
}
void query(int node, int l, int r) {
if (a <= l && r <= b)
result += tree[node];
else {
int m = (l + r) >> 1;
if (a <= m) query(node << 1, l, m);
if (b > m) query((node << 1) + 1, m + 1, r);
}
}
void construct(int node, int l, int r) {
if (l == r)
tree[node] = 1;
else {
int m = (l + r) >> 1;
construct(node << 1, l, m);
construct((node << 1) + 1, m + 1, r);
tree[node] = tree[node << 1] + tree[(node << 1) + 1];
}
}
int search(int count) {
int pos = 0;
int step = 1 << 17;
while (step >>= 1) {
if (pos + step <= n) {
a = 1;
b = pos + step;
result = 0;
query(1, 1, n);
if (result < count)
pos += step;
}
}
return pos + 1;
}
int main() {
int64 answer = 0;
int64 count = 0;
in >> n >> k;
construct(1, 1, n);
for (int i = 1; i <= n; ++i) {
count = k - 1LL * (n - i) * (n - i - 1) / 2;
if (count < 0)
position = search(1);
else {
position = search(count + 1);
k -= count;
}
update(1, 1, n);
out << position << ' ';
}
return 0;
}