Pagini recente » Borderou de evaluare (job #2900145) | Borderou de evaluare (job #3324567) | Profil aardvark | Cod sursa (job #3363944) | Cod sursa (job #3364543)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("order.in");
ofstream cout("order.out");
int n;
class FenwickTree {
vector<int> tree;
int size;
void update_(int pos) {
for (int i = pos ; i <= n ; i += i & -i) {
tree[i] -= 1;
}
}
int query_(int pos) {
int ans = 0;
for (int i = pos ; i > 0 ; i -= i & -i) {
ans += tree[i];
}
return ans;
}
public:
FenwickTree(int size) {
this->size = size;
tree.assign(size + 2, 0);
for (int i = 1 ; i <= size ; ++i) {
tree[i] = i & -i;
}
}
void update(int pos) {
update_(pos);
}
int exact_sum_position(int sum) {
int ans_idx = 0, current_sum = 0;
for (int i = 1 << 30 ; i > 0 ; i >>= 1) {
if (ans_idx + i <= n && current_sum + tree[ans_idx + i] < sum) {
ans_idx += i;
current_sum += tree[ans_idx];
}
}
if (ans_idx + 1 > n || query_(ans_idx + 1) != sum) {
return -1;
}
return ans_idx + 1;
}
};
int main() {
cin >> n;
int r = 2;
FenwickTree t(n);
for (int i = 1 ; i <= n ; ++i) {
int remaining = n - i + 1;
r = ((r + i - 2) % remaining) + 1;
int ans_idx = t.exact_sum_position(r);
cout << ans_idx << " ";
t.update(ans_idx);
}
return 0;
}