Cod sursa(job #2381650)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 17 martie 2019 11:40:18
Problema Schi Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#define MaxN 30000
#define DIM 174

using namespace std;

ifstream f ("schi.in");
ofstream g ("schi.out");

int n;

int sol[MaxN + 5];

int v[MaxN+5];
int BATON[DIM+DIM];

bool NEAT[MaxN + 5];

void scad (int poz)
{
    int bucata = poz / DIM;
    if (poz % DIM != 0) bucata++;

    BATON[bucata]--;
    NEAT[poz] = 1;
}

int sume (int poz)
{
    int lim_poz = (poz / DIM) * DIM + 1;
    int rez = 0;

    for (int i = lim_poz; i <= poz; ++i)
    {
        rez = rez + 1 - NEAT[i];
    }

    int bucata_poz = poz / DIM;
    if (poz % DIM != 0) bucata_poz++;

    for (int i = 1; i < bucata_poz; ++i)
        rez = rez + BATON[i];

    return rez;
}

int main()
{
    f >> n;

    for (int i = 1; i <= n; ++i) {
        f >> v[i];
        BATON[i] = DIM;
    }

    if (n % DIM != 0)
    {
        int bucata = n / DIM + 1;
        BATON[bucata] = n - (n / DIM) * DIM;
    }

    for (int i = n; i >= 1; --i)
    {
        int st = 1;
        int dr = n;
        int L = n + 1;

        while (st <= dr)
        {
            int mij = (st + dr) / 2;

            if (sume(mij) == v[i] && mij < L && NEAT[mij] == 0)
            {
                L = mij;
                dr = mij - 1;
            }
            else if (sume(mij) < v[i])
            {
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }

        sol[L] = i;
        scad(L);
    }

    for (int i = 1; i <= n; ++i)
        g << sol[i] << '\n';
    return 0;
}