Pagini recente » Cod sursa (job #324365) | Cod sursa (job #391966) | Cod sursa (job #1101205) | Cod sursa (job #1432095) | Cod sursa (job #3168479)
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
const int Nmax = 30005;
int n,aib[4*Nmax];
void update(int x, int y){
for(int i=x;i<=n;i+=(i&(-i)))
aib[i]+=y;
}
int query0(int x){
if(x == 0)
return 0;
int s = 0;
for(int i=x;i>0;i-=(i&(-i)))
s+=aib[i];
return s;
}
int query(int x, int pas){
if(x == 0)
return 0;
if(x>n){
x = x%n;
if(x == 0)
x = n;
return (query0(x)+n-pas+1);
}
return query0(x);
}
int main()
{
int i,j,pos,st,dr,mid,sol = 0;
fin >> n;
for(i=1;i<=n;i++)
update(i,1);
pos = 1;
for(i=1;i<=n;i++){ /// sa nu uiti sa faci ca n sa devina 0 la final;
st = pos+1; dr = n+pos; j = i%(n-i+1);
if(j == 0)
j = n-i+1;
while(st<=dr){
mid = (st+dr)/2;
int val = query(pos,i);
if(query(mid,i)-val>=j){
dr = mid-1;
sol = mid;
}
else
st = mid+1;
}
sol%=n;
if(sol == 0)
sol = n;
fout << sol << " ";
update(sol,-1);
pos = sol%n;
}
return 0;
}