Pagini recente » Cod sursa (job #585329) | Cod sursa (job #1188318) | Cod sursa (job #299230) | Cod sursa (job #1352746) | Cod sursa (job #1361831)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("farfurii.in");
ofstream out("farfurii.out");
const int Nmax = 100005;
const int tree_size = 262144;
int n, k;
int tree[tree_size];
int taken[Nmax];
int position, value, result, a, b;
void update(int node, int l, int r) {
if (l == r)
tree[node] = value;
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);
}
}
int main() {
int p, q;
in >> n >> k;
p = q = 1;
for (int i = 1; i <= n; ++i) {
int nr = (n - i) * (n - i - 1) / 2;
int need = k - nr;
if (need < 0) need = 0;
if (!need) {
while (taken[p]) ++p;
out << p << ' ';
position = p;
value = 1;
update(1, 1, n);
taken[p] = 1;
++p;
}
else {
q = p - 1;
do {
++q;
while (taken[q]) ++q;
a = 1;
b = q - 1;
result = 0;
query(1, 1, n);
} while ((q - 1 - result) < need);
taken[q] = 1;
position = q;
value = 1;
update(1, 1, n);
out << q << ' ';
k -= need;
if (p == q) ++p;
}
}
return 0;
}