Cod sursa(job #2489323)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 8 noiembrie 2019 15:13:07
Problema Schi Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#define NMAX 30005
#define ub(x) (x & -x)

using namespace std;

int aib[NMAX], clas[NMAX], v[NMAX], n;

void update(int p)
{
    for (int i = p; i <= n; i += ub(i))
        aib[i]++;
}

int query(int p)
{
    int64_t suma = 0;
    for (int i = p; i >= 1; i -= ub(i))
        suma += aib[i];
    return suma;
}

int bsearch(int p, int u, int key)
{
    int m;
    while (p <= u)
    {
        m = (p + u) / 2;
        if(m - query(m) <= key) p = m + 1;
        else u = m - 1;
    }
    m = (p + u) / 2;
    if (m - query(m) > key) m--;
    while (m - query(m) == key && m) m--;
    return m + 1;
}

class InParser
{
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch()
    {
        ++sp;
        if (sp == 4096)
        {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }
public:
    InParser(const char* nume)
    {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }
    InParser& operator >> (int &n)
    {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else n = c - '0';
        while(isdigit(c = read_ch())) n = 10 * n + c - '0';
        n *= sgn;
        return *this;
    }
    InParser& operator >> (long long &n)
    {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else n = c - '0';
        while (isdigit(c = read_ch())) n = 10 * n + c - '0';
        n *= sgn;
        return *this;
    }
};

int main()
{
    InParser fin("schi.in");
    ofstream fout("schi.out");

    fin >> n;

    for (int i = 1; i <= n; ++i)
        fin >> v[i];

    for (int i = n; i >= 1; --i)
    {
        int p = bsearch(v[i], n, v[i]);
        clas[p] = i;
        update(p);
    }

    for (int i = 1; i <= n; ++i)
        fout << clas[i] << "\n";

    return 0;
}