Pagini recente » Cod sursa (job #3149621) | Cod sursa (job #2898162) | Cod sursa (job #2897854) | Cod sursa (job #1455621) | Cod sursa (job #3248360)
#include <iostream>
#include <fstream>
#include <math.h>
const int MAXN=3e4;
const int MAXBIT=15;
struct BIT{
int aib[MAXN+1], n, i;
void init(int _n){
this->n=_n;
for(i=0; i<=n; i++)
aib[i]=i&-i;
}
void update_pref_sum(int poz, int val){
update(poz, val);
}
void update(int poz, int val){
for(; poz<=n; poz+=poz&-poz)
aib[poz]+=val;
}
int get_pref_sum(int poz){
return query(poz);
}
int query(int poz){
int ans=0;
for(; poz>0; poz&=(poz-1))
ans+=aib[poz];
return ans;
}
int bin_search(int k){
int ans=0;
for(i=MAXBIT; i>=0; i--)
if(ans+(1<<i)<=n && aib[ans+(1<<i)]<k)
k-=aib[ans+=(1<<i)];
return ans+1;
}
};
BIT aib;
int main()
{
std::ifstream cin("order.in");
std::ofstream cout("order.out");
int n, cate, poz, last, x, i;
cin>>n;
aib.init(n);
cout<<"2 ";
aib.update_pref_sum(2, -1);
last=2;
for(i=1; i<n; i++){
cate=(n-i);
poz=i%(n-i)+1;
x=aib.get_pref_sum(last);
if(cate-x>=poz)
last=aib.bin_search(x+poz);
else
last=aib.bin_search(poz-(cate-x));
cout<<last<<" ";
aib.update_pref_sum(last, -1);
}
return 0;
}