Pagini recente » Cod sursa (job #1351188) | Cod sursa (job #2798499) | Cod sursa (job #1840062) | Cod sursa (job #325109) | Cod sursa (job #2262915)
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int N, pow = 1;
int aib[30005];
inline int LastBit(int x)
{
return x & (-x);
}
void Update(int pos, int val)
{
for(int i = pos; i <= N; i += LastBit(i))
aib[i] += val;
}
int Query(int pos)
{
int answer = 0;
for(int i = pos; i > 0; i -= LastBit(i))
answer += aib[i];
return answer;
}
int Search(int val)
{
int cursor = 0;
for(int step = pow; step > 0; step >>= 1)
if(cursor + step <= N && aib[cursor + step] < val)
{
cursor += step;
val -= aib[cursor];
}
return cursor + 1;
}
int main()
{
fin >> N;
for(; pow <= N; pow <<= 1);
for(int i = 1; i <= N; i++)
Update(i, 1);
fout << 2 << ' ';
Update(2, -1);
int currentPos = 2;
for(int i = 2; i <= N; i++)
{
int realSteps = i % Query(N);
int posRight = Query(N) - Query(currentPos);
int posLeft = Query(currentPos);
int elimPos;
if(realSteps == 0 && posLeft == 0)
realSteps = 1;
if(realSteps > posRight)
elimPos = Search(realSteps - posRight);
else
elimPos = Search(realSteps + posLeft);
fout << elimPos << ' ';
Update(elimPos, -1);
currentPos = elimPos;
}
return 0;
}