Pagini recente » Cod sursa (job #869170) | Cod sursa (job #1370769) | Cod sursa (job #3253939) | Cod sursa (job #1963618) | Cod sursa (job #3267247)
#include <bits/stdc++.h>
using namespace std;
/**
order
baruri
schi
distincte
mate
intervale2
unique
*/
ifstream fin("order.in");
ofstream fout("order.out");
int aib[100005], n;
void Update(int p, int x)
{
for ( ; p <= n; p += (p & -p))
aib[p] += x;
}
int Query(int p)
{
int s = 0;
for ( ; p > 0; p -= (p & -p))
s += aib[p];
return s;
}
int SearchFw(int p, int x)
{
int st, dr, mij, ind, s;
st = p + 1; dr = n; ind = -1;
s = Query(p);
while (st <= dr)
{
mij = (st + dr) / 2;
if (Query(mij) - s >= x)
{
ind = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
return ind;
}
int Search(int x)
{
int st, dr, mij, ind;
st = 1; dr = n; ind = -1;
while (st <= dr)
{
mij = (st + dr) / 2;
if (Query(mij) >= x)
{
ind = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
return ind;
}
int main()
{
int i, p, x;
fin >> n;
for (i = 1; i <= n; i++)
Update(i, 1);
p = 1;
for (i = 0; i < n; i++)
{
x = Query(n) - Query(p);
if (x > (i + 1) % (n - i))
p = SearchFw(p, (i + 1) % (n - i));
else
p = Search((i + 1) % (n - i) - x);
Update(p, -1);
fout << p << " ";
}
return 0;
}