Cod sursa(job #2156612)

Utilizator DavidLDavid Lauran DavidL Data 8 martie 2018 20:58:53
Problema Schi Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#define MAX 30005
using namespace std;
ifstream fi("schi.in");
ofstream fo("schi.out");

int n,x[MAX],rez[MAX];
int A[MAX];

int query(int poz)
{
    int rez=0;
    while (poz)
    {
        rez+=A[poz];
        poz-=((poz^(poz-1))&poz);
    }
    return rez;
}

void update(int poz)
{
    while (poz<=n)
    {
        A[poz]++;
        poz+=((poz^(poz-1))&poz);
    }
}

int main()
{
    fi>>n;
    for (int i=1; i<=n; i++)
        fi>>x[i];

    for (int i=n; i>=1; i--)
    {
        int poz=x[i]+query(x[i]);
        while (rez[poz]) /// sper
            poz++;
        rez[poz]=i;
        //fo<<i<<" ocupa "<<x[i]+query(x[i])<<"\n";
        update(x[i]);
    }
    for (int i=1; i<=n; i++)
        fo<<rez[i]<<"\n";
    return 0;
}