Pagini recente » Cod sursa (job #55489) | Cod sursa (job #3179186) | Cod sursa (job #2567231) | Cod sursa (job #1959184) | Cod sursa (job #1509092)
#include <fstream>
using namespace std;
ifstream fin ("order.in");
ofstream fout ("order.out");
int n, AIB[100010];
inline int zeros(int &x)
{
return (x ^ (x - 1) & x);
}
void Update(int poz, int value)
{
while (poz <= n)
{
AIB[poz] += value;
poz += zeros(poz);
}
}
int Query(int poz, int sum = 0)
{
while (poz)
{
sum += AIB[poz];
poz -= zeros(poz);
}
return sum;
}
inline int Binary_Search(int value, int st, int dr)
{
int step = 1, ok = 0;
while (step <= dr) step <<= 1;
while (step)
{
step >>= 1;
if (dr - step >= st)
{
int aux = Query(dr - step) - Query(st - 1);
if (aux >= value)
{
dr -= step;
ok = 1;
}
}
}
if (ok) return dr;
return 0;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
Update(i, 1);
}
int m = n, ppp = 1;
for (int i = 1; i <= n; i++)
{
int aux = i;
aux %= m;
if (!aux) aux = m;
if (Binary_Search(1, ppp + 1, n))
{
ppp = Binary_Search(1, ppp + 1, n);
}
else
{
ppp = Binary_Search(1, 1, ppp);
}
if (Binary_Search(aux, ppp, n))
{
ppp = Binary_Search(aux, ppp, n);
}
else
{
aux -= Query(n) - Query(ppp - 1);
ppp = Binary_Search(aux, 1, ppp);
}
fout << ppp << ' ';
Update(ppp, -1);
m --;
}
fout.close();
return 0;
}