Pagini recente » Cod sursa (job #2678202) | Cod sursa (job #2634478) | Cod sursa (job #2452127) | Cod sursa (job #1705276) | Cod sursa (job #2777077)
#include <fstream>
#include <vector>
std::vector <int> aib;
void update(int pos) {
while (pos < aib.size()) {
aib[pos]--;
pos += (pos & -pos);
}
}
int query(int pos) {
int ans = 0;
while (pos) {
ans += aib[pos];
pos &= (pos - 1);
}
return ans;
}
int main() {
std::ifstream fin("order.in");
std::ofstream fout("order.out");
int nrn;
int pos;
int pos1, pos2, mid;
fin >> nrn;
for (int index = 0; index <= nrn; index++) {
aib.push_back(index & -index);
}
pos = 1;
for (int index = 0; index < nrn; index++) {
pos += index;
pos %= nrn - index;
pos++;
pos1 = 0;
pos2 = nrn;
while (pos2 - pos1 > 1) {
mid = (pos1 + pos2) / 2;
if (query(mid) < pos) {
pos1 = mid;
}
else {
pos2 = mid;
}
}
fout << pos2 << ' ';
update(pos2);
pos--;
}
}