Pagini recente » Cod sursa (job #89308) | Cod sursa (job #1808970) | Cod sursa (job #1483901) | Cod sursa (job #1963583) | Cod sursa (job #3304168)
#include <fstream>
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
const int nmax = 30000;
int n, nrq, type, a, b;
int value;
inline int f(int x){ return (x & (-x)); }
struct fenwicktree{
int tree[nmax + 2], intotal;
void add(int pos, int val){
for(int i = pos; i <= n; i += f(i))
tree[i] += val;
intotal += val;
}
int sum(int pos){
int s = 0;
for(int i = pos; i >= 1; i -= f(i))
s += tree[i];
return s;
}
int getkth(int k){
int pos = 0;
for(int b = 14; b >= 0; b--){
if((pos | (1 << b)) <= n && tree[pos | (1 << b)] < k)
pos |= (1 << b), k -= tree[pos];
}
return pos + 1;
}
} aib;
int main(){
in>>n; aib.intotal = n;
for(int i = 1; i <= n; i++){
aib.tree[i] += 1;
if(i + f(i) <= n)
aib.tree[i + f(i)] += aib.tree[i];
}
for(int i = 1, child = 1; i <= n; i++){
int k = i + aib.sum(child);
k %= aib.intotal;
if(!k) k = aib.intotal;
k = aib.getkth(k);
aib.add(k, -1);
out<<k<<" ";
child = k;
}
return 0;
}