Cod sursa(job #1629026)

Utilizator DiClauDan Claudiu DiClau Data 4 martie 2016 12:14:06
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 i,int x)
{
    while(i<=n)
    {
        aib[i]+=x;
        i+=((i^(i-1))&i);
    }
}

long interog(int i)
{
    long s=0;
    while(i>0)
    {
        s+=aib[i];
        i-=((i^(i-1))&i);//(1<<nr0(i));
    }
    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;
}