Pagini recente » Cod sursa (job #1992562) | Cod sursa (job #2203398) | Cod sursa (job #1855417) | Cod sursa (job #774384) | Cod sursa (job #2290208)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("datorii.in");
ofstream fout("datorii.out");
int n;
int tree[120001];
void build(int node, int left, int right) {
if (left == right) {
tree[node] = 1;
return;
}
int mid = (left + right) / 2;
build(2*node, left, mid);
build(2*node + 1, mid + 1, right);
tree[node] = tree[2*node] + tree[2*node + 1];
}
int query(int node, int left, int right, int person) {
tree[node]--;
if (left == right) {
return left;
} else {
int mid = (left + right) / 2;
if (person <= tree[2*node]) {
query(2*node, left, mid, person);
} else {
query(2*node + 1, mid + 1, right, person - tree[2*node]);
}
}
}
int main() {
fin >> n;
build(1, 1, n);
int personsNum = n, prevLoser = 2;
for (int skip = 1; skip <= n; skip++) {
personsNum = tree[1];
int nextLoser = (prevLoser + skip - 1) % personsNum;
if (nextLoser == 0) {nextLoser = personsNum;}
fout << query(1, 1, n, nextLoser) << " ";
personsNum--;
prevLoser = nextLoser;
}
return 0;
}