Pagini recente » Cod sursa (job #2769248) | Cod sursa (job #1150896) | Cod sursa (job #517597) | Cod sursa (job #557783) | Cod sursa (job #2944723)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
struct SegmentTree {
vector <int> seg;
SegmentTree(int n = 0) {
seg.resize(4 * n);
}
void update(int node, int from, int to, int pos, int x) {
if(from == to) {
seg[node] = x;
}else {
int mid = (from + to) / 2;
if(pos <= mid) {
update(node * 2, from, mid, pos, x);
}else {
update(node * 2 + 1, mid+1, to, pos, x);
}
seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
}
int query(int node, int from, int to, int x, int y) {
if(from == x && to == y) {
return seg[node];
}else {
int mid = (from + to) / 2, ans = 0;
if(x <= mid) {
ans += query(node * 2, from, mid, x, min(mid, y));
}
if(mid < y) {
ans += query(node * 2 + 1, mid+1, to, max(mid + 1, x), y);
}
return ans;
}
}
};
int main() {
int n, m;
in >> n;
m = n;
SegmentTree seg(n);
int last = 2;
for(int i = 1;i <= n;i++) {
int target = (last + i - 1) % m, index, from = 1, to = n;
if(target == 0) {
target = m;
}
while(from != to) {
int mid = (from + to) / 2;
//cout << from << ' ' << to << ' ' << mid << '\n';
if(mid - seg.query(1, 1, n, 1, mid) >= target) {
to = mid;
}else {
from = mid+1;
}
}
out << from << ' ';
seg.update(1, 1, n, from, 1);
last = target;
m = m - 1;
}
return 0;
}