Cod sursa(job #3322393)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 13 noiembrie 2025 19:25:46
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#include <string.h>
#define NMAX 30005
#define ub(x) (x & -x)
#include <stdio.h>
#include <ctype.h>

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;
    }
};

using namespace std;

ofstream fout("schi.out");

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

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

int query(int p)
{
    int 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 (query(m) <= key)
            p = m + 1;
        else
            u = m - 1;
    }

    m = (p + u) / 2;

    if (query(m) > key)
        m--;
    while (query(m) == key && m)
        m--;

    m++;

    if (query(m) == key)
        return m;
    return -1;
}

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

    fin >> n;

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

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

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

    return 0;
}