Pagini recente » Cod sursa (job #3330262) | Profil RaresH | Cod sursa (job #3347458) | Cod sursa (job #3322894) | Cod sursa (job #3339409)
#include <fstream>
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
int n;
int aib[60005];
void build()
{
for(int i = 1; i<=2*n; i++)
{
aib[i]++;
int nxt = i + (i&-i);
if(nxt <= 2 * n)
{
aib[nxt] += aib[i];
}
}
}
void update(int poz, int val)
{
for(int i = poz; i<=2*n; i+=(i&-i))
{
aib[i] += val;
}
}
int query(int poz)
{
int ans = 0;
for(int i = poz; i>=1; i-=(i&-i))
{
ans += aib[i];
}
return ans;
}
int norm(int x)
{
if(x <= n)
{
return x;
}
return x - n;
}
int ech(int x)
{
if(x <= n)
{
return x + n;
}
return x - n;
}
int main()
{
in>>n;
build();
int poz = 2;
for(int i = 1; i<=n; i++)
{
int ramas = n - i + 1;
int moves = (i % ramas);
if(moves == 0)
{
moves = ramas;
}
int st = poz;
int dr = 2 * n;
int ans = -1;
int mij;
while(st <= dr)
{
mij = (st + dr) / 2;
if(query(mij) - query(poz - 1) >= moves)
{
ans = mij;
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
if(ans == -1)
{
return 1;
}
out<<norm(ans)<<" ";
update(ans, -1);
update(ech(ans), -1);
poz = norm(ans);
}
return 0;
}