Pagini recente » Cod sursa (job #1923840) | Cod sursa (job #1643498) | Cod sursa (job #355559) | Cod sursa (job #1341466) | Cod sursa (job #1477755)
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
using namespace std;
const string name = "order",
in_file = name + ".in",
out_file = name + ".out";
ifstream fin(in_file);
ofstream fout(out_file);
const int MAX = 3e4 + 5;
int n, aib[MAX], viz[MAX], pmax = 1;
int lsb(int nr) {
return nr & (-nr);
}
void update(int poz, int val) {
for (int i = poz; i <= n; i += lsb(i))
aib[i] += val;
}
int query(int nr) {
int sol = 0;
for (int p = pmax; p >= 1 && nr; p /= 2)
if (sol + p <= n && aib[sol + p] <= nr) {
nr -= aib[sol + p];
sol += p;
}
while (viz[sol])
sol--;
return sol;
}
int main() {
fin >> n;
while (pmax * 2 <= n)
pmax *= 2;
for(int i = 1; i <= n; i++)
update(i, 1);
for(int x = 2, ind, mod, i = 1; i <= n; i++) {
mod = n - i + 1;
x = (x + n - mod) % mod;
if (!x)
x = mod;
ind = query(x);
update(ind, -1);
viz[ind] = 1;
fout << ind << ' ';
}
return 0;
}