Pagini recente » Cod sursa (job #3146785) | Cod sursa (job #359999) | Cod sursa (job #1038930) | Cod sursa (job #35227) | Cod sursa (job #3267323)
#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], a[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 = p;
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, nr;
fin >> n;
for (i = 1; i <= n; i++)
{
Update(i, 1);
a[i] = 1;
}
p = 1;
for (i = 0; i < n; i++)
{
x = Query(n) - Query(p);
//cout << (i + 1) % (n - i) << " " << x << "\n";
if ((i + 1) % (n - i) == 0 && x == 0)
{
while (a[p] == 0)
p--;
}
else if ((i + 1) % (n - i) == 0 && x > 0)
while (a[p] == 0)
p++;
else
{
if (x >= (i + 1) % (n - i))
p = SearchFw(p, (i + 1) % (n - i));
else
p = Search((i + 1) % (n - i) - x);
}
Update(p, -1);
a[p] = 0;
fout << p << " ";
}
return 0;
}