Cod sursa(job #2381735)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 17 martie 2019 12:51:03
Problema Schi Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 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 - 1) / DIM;

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

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

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

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

    int bucata = (n + DIM - 1) / DIM;
    BATON[bucata] = n - (bucata-1) * DIM;

    for (int i = n; i > 0; --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] == false)
            {
                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;
}