Pagini recente » Cod sursa (job #2382959) | Cod sursa (job #2157542) | Cod sursa (job #1874217) | Cod sursa (job #2117136) | Cod sursa (job #1811960)
#include<fstream>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
/*
we use segment tree to determine the i'th element in the list in log time
*/
long long arb[300009];
/*
updates a value
*/
void update(long long n, long long l, long long r, long long pos, long long val) {
if (l == r) {
arb[n] = val;
return;
}
long long m = (l + r) / 2;
if (pos <= m) {
update(n * 2, l, m, pos, val);
}
else {
update(n * 2 + 1, m + 1, r, pos, val);
}
arb[n] = arb[n * 2] + arb[n * 2 + 1];
}
/*
gets the position of the i'th element
*/
void position(long long n, long long l, long long r, long long i, long long& pos) {
if (l == r) {
pos = l;
return;
}
long long m = (l + r) / 2;
if (i <= arb[n * 2]) {
position(n * 2, l, m, i, pos);
}
else {
position(n * 2 + 1, m + 1, r, i - arb[n * 2], pos);
}
}
/*
creates the inversion table
*/
void make_inversions(long long n, long long k, long long inversions[]) {
long long idx = n - 1;
long long amount = k; long long value = 1;
while (amount != 0) {
if (amount < value) {
value = amount;
amount = 0;
} //stopping condition
else {
amount -= value;
}
inversions[idx] = value;
idx--;
value++;
}
}
int main() {
long long n, k;
long long inversions[100009];
long long farfurii[100009];
fin >> n >> k;
for (long long i = 1; i <= n; i++) {
farfurii[i] = i;
inversions[i] = 0;
update(1, 1, n, i, 1);
}
make_inversions(n, k, inversions);
for (long long i = 1; i <= n; i++) {
long long init_pos = inversions[i] + 1;
long long actual_pos = 0;
position(1, 1, n, init_pos, actual_pos);
fout << farfurii[actual_pos] << " ";
update(1, 1, n, actual_pos, 0);
}
}