Pagini recente » Cod sursa (job #1735468) | Cod sursa (job #210187) | Cod sursa (job #759437) | Istoria paginii runda/sim.oji.2012/clasament | Cod sursa (job #950565)
Cod sursa(job #950565)
#include <fstream>
using namespace std;
int N, P;
int AIB[30002];
void update(int pos)
{
for (; pos <= N; pos += pos & -pos)
++AIB[pos];
}
int query(int pos)
{
int sum = 0;
for (; pos >= 1; pos -= pos & -pos)
sum += AIB[pos];
return sum;
}
int main()
{
ifstream fin("order.in");
ofstream fout("order.out");
fin >> N;
P = 1;
for (int i = 1; i <= N; ++i) // caut al i-lea
{
int pas = i % (N - i + 1);
if (pas == 0) pas = N - i + 1;
if (N - P - (query(N) - query(P)) >= pas)
{
int step = 1 << 14, resnow;
for (resnow = P - 1; step; step >>= 1)
if (resnow + step <= N && (resnow + step) - P - (query(resnow + step) - query(P)) < pas)
resnow += step;
++resnow;
P = resnow;
}
else
{
int sub = pas - (N - P - (query(N) - query(P)));
int step = 1 << 14, resnow;
for (resnow = 0; step; step >>= 1)
if (resnow + step <= N && (resnow + step) - query(resnow + step) < sub)
resnow += step;
++resnow;
P = resnow;
}
fout << P << ' ';
update(P);
}
fout << '\n';
fin.close();
fout.close();
}