Pagini recente » Cod sursa (job #422511) | Cod sursa (job #2677239) | Cod sursa (job #1335455) | Cod sursa (job #1454109) | Cod sursa (job #1462197)
#include <cstdio>
#define nmax 31000
using namespace std;
int N,AIB[nmax];
bool v[nmax];
inline void Update(int x , int poz){
for(int i = poz; i <= N; i+=(i&-i))
AIB[i]+=x;
}
inline int Compute(int x){
int s = 0;
for(int i = x; i; i-=(i&-i))
s+=AIB[i];
return s;
}
int main(){
int i,x,y,s,j,k,q,ult,l,r,mid,sol;
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
scanf("%d",&N);
for(i = 1; i <= N; ++i)
Update(1,i);
ult = 1;
for(i = 1; i <= N; ++i){
x = Compute(N) - Compute(ult-1);
if(x >= i){
l = ult + 1;
r = N;
while(l <= r){
mid = (l + r)>>1;
if(Compute(mid) - Compute(ult) == i && !v[mid]){
sol = mid;
r = mid - 1;
}
else if(Compute(mid) - Compute(ult) < i)
l = mid + 1;
else r = mid - 1;
}
ult = sol;
printf("%d ",sol);
v[sol] = 1;
Update(-1,sol);
continue;
}
l = 1;
r = N;
j = i - x;
j%=Compute(N);
if(!j) j = Compute(N);
while(l <= r){
mid = (l + r)>>1;
if(Compute(mid) == j && !v[mid]){
sol = mid;
r = mid - 1;
}
else if(Compute(mid) < j)
l = mid + 1;
else r = mid - 1;
}
ult = sol;
v[sol] = 1;
Update(-1,sol);
printf("%d ",sol);
}
return 0;
}