Pagini recente » Cod sursa (job #3037129) | Cod sursa (job #542000) | Cod sursa (job #1463051) | Cod sursa (job #2829710) | Cod sursa (job #1509093)
#include <fstream>
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
int n, AIB[30003];
inline int zeros (int x)
{
return x & (-x);
}
inline void Update (int poz, int val)
{
for (; poz <= n; poz += zeros(poz))
{
AIB[poz] += val;
}
}
inline int Query (int poz, int sum = 0)
{
for (; poz; poz -= zeros (poz))
{
sum += AIB[poz];
}
return sum;
}
inline int BinSearch (int val, int st, int dr)
{
int step;
bool gasit =false;
for (step = 1; step <= dr; step <<= 1);
while (step)
{
step >>= 1;
if (dr - step >= st)
{
int aux = Query (dr - step) - Query (st - 1);
if ( aux >= val)
{
dr -= step;
gasit = true;
}
}
}
if (gasit == true) return dr;
return 0;
}
int main ()
{
in >> n;
for (int i = 1; i <= n; i++)
{
Update (i, 1);
}
int ramase = n, pos = 1;
for (int i = 1; i <= n; i++)
{
int aux = i;
aux %= ramase;
if (!aux) aux = ramase;
if (BinSearch(1, pos +1, n))
{
pos = BinSearch(1, pos +1, n);
}
else
{
pos = BinSearch(1, 1, pos);
}
if (BinSearch(aux, pos, n))
{
pos = BinSearch(aux, pos, n);
}
else
{
aux -= Query(n) - Query(pos - 1);
pos = BinSearch(aux, 1, pos);
}
Update (pos, -1);
ramase --;
out << pos << ' ';
}
}