Pagini recente » Cod sursa (job #712269) | Cod sursa (job #1231269) | Cod sursa (job #2775348) | Cod sursa (job #3253539) | Cod sursa (job #1629030)
#include<stdio.h>
using namespace std;
const int N = 30005;
int v[N], aib[2 << 15], sol[N];
int n;
void actualizare (int x, int val)
{
while (x <= n)
{
aib[x] += val;
x += x & (-x);
}
}
int interog (int x)
{
int s = 0;
while (x > 0)
{
s += aib[x];
x -= x & (-x);
}
return s;
}
int main ()
{
FILE *in, *out;
in = fopen ("schi.in", "r");
out = fopen ("schi.out", "w");
fscanf (in, "%d", &n);
int i;
for (i = 1; i <= n; i++)
fscanf (in, "%d", &v[i]);
int nr, st, dr, x, aux, pas = 1;
while (pas <= n)
pas <<= 1;
pas >>= 1;
aux = pas;
for (i = n; i >= 1; i--)
{
nr = interog (v[i] - 1) + 1;
if (nr > 1 || (nr == 1 && aib[v[i]] >= 1))
{
st = v[i];
dr = 0;
pas = aux;
while (pas != 0)
{
if (dr + pas <= n && dr - st + pas + 1 - (interog (dr + pas) - interog (st - 1)) < nr)
dr += pas;
pas >>= 1;
}
{
sol[dr + 1] = i;
actualizare (dr + 1, 1);
}
}
else
{
sol[v[i]] = i;
actualizare (v[i], 1);
}
}
for (i = 1; i <= n; i++)
fprintf (out, "%d\n", sol[i]);
return 0;
}