Pagini recente » Cod sursa (job #1782537) | Cod sursa (job #1199804) | Cod sursa (job #2771937) | Cod sursa (job #280249) | Cod sursa (job #1660334)
#include <algorithm>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
class Aib {
private:
int dim;
vector<int> aib;
inline int lsb(int x) {
return (x & (-x));
}
public:
Aib(int dim) {
this->dim = dim;
aib.resize(dim + 5, 0);
}
void update(int pos, int val) {
for (int i = pos; i <= dim; i += lsb(i))
aib[i] += val;
}
int query1(int pos) {
int ans = 0;
for (int i = pos; i; i -= lsb(i))
ans += aib[i];
return ans;
}
int query2(int val) {
int sum = 0, step = 1;
while (step < dim)
step <<= 1;
int i;
for (i = 0; step; step >>= 1) {
if (i + step > dim)
continue;
if (sum + aib[i + step] < val) {
sum += aib[i + step];
i += step;
}
}
if (i < dim && query1(i + 1) == val)
return i + 1;
else
return -1;
}
} *aib;
int main() {
int n;
fin >> n;
aib = new Aib(n);
for (int i = 1; i <= n; ++i)
aib->update(i, 1);
int curr = 1;
for (int i = 1; i <= n; ++i) {
curr = (curr + i) % (n - i + 1);
if (curr == 0)
curr = n - i + 1;
int pos = aib->query2(curr);
fout << pos << ' ';
--curr;
aib->update(pos, -1);
}
fout << '\n';
return 0;
}
//Trust me, I'm the Doctor!