Cod sursa(job #1628996)

Utilizator DiClauDan Claudiu DiClau Data 4 martie 2016 12:03:14
Problema Schi Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#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;
}