Pagini recente » Cod sursa (job #1563231) | Cod sursa (job #1065056) | Cod sursa (job #2027751) | Cod sursa (job #2601768) | Cod sursa (job #2262421)
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int N, pow = 1;
int aib[30005];
bool d[30005];
inline int LastBit(int x)
{
return x & (-x);
}
void Update(int poz, int val)
{
for(int i = poz; i <= N; i += LastBit(i))
aib[i] += val;
}
int Query(int poz)
{
int answer = 0;
for(int i = poz; 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);
int currentPos = 1;
for(int i = 1; i <= N - 1; i++)
{
int realSteps = i % Query(N);
int posR = Query(N) - Query(currentPos - 1);
int posL = Query(currentPos);
int elimPos;
if(realSteps > posR)
elimPos = Search(realSteps - posR);
else
elimPos = Search(realSteps + posL);
d[elimPos] = 1;
fout << elimPos << ' ';
Update(elimPos, -1);
currentPos = elimPos;
}
for(int i = 1; i <= N; i++)
if(!d[i])
{
fout << i;
break;
}
return 0;
}