Cod sursa(job #2415095)

Utilizator marinaoprOprea Marina marinaopr Data 25 aprilie 2019 15:26:39
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb




#include <stdio.h>

#define it(x) x&(-x)
#define NMAX 30005

using namespace std;

FILE *fin = fopen("schi.in", "r");
FILE *fout = fopen("schi.out", "w");

int n,a[NMAX],aib[NMAX],i,ans[NMAX],loc;

void update(int poz)
{
    for(int i=poz; i<=n; i+=it(i))
        aib[i]--;
}

int sum(int poz)
{
    int rez = 0;

    for(int i=poz; i>=1; i-=it(i))
        rez += aib[i];

    return rez;
}

int query(int poz)
{
    int left = 1;
    int right = n,mid;
    int rez = -1;
    while(left <= right)
    {
        mid = (left+right) /2;

        if(sum(mid) >= poz)
        {
            rez = mid;
            right = mid-1;
        }
        else
            left = mid+1;
    }

    return rez;
}

int main()
{
    fscanf(fin, "%d", &n);
    for(i=1; i<=n; ++i)
    {
        fscanf(fin, "%d", &a[i]);
        aib[i] = it(i);
    }

    for(i=n; i>=1; --i)
    {
        loc = query(a[i]);
        ans[loc] = i;
        update(loc);
    }

    for(i=1; i<=n; ++i)
        fprintf(fout, "%d\n", ans[i]);

    fclose(fin);
    fclose(fout);
    return 0;
}