Cod sursa(job #3243194)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 16 septembrie 2024 15:02:53
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "schi";

std :: ifstream in (FILENAME + ".in");

std :: ofstream out (FILENAME + ".out");

const int NMAX = 3e4 + 5;

int n;

int x;

int y;

int c;

int i;

int v[NMAX];

int arb[4 * NMAX];

std :: vector <std :: pair <int, int>> ans;

void update(int nod, int st, int dr)
{
    if(st == dr)
    {
        arb[nod] = 1;
    }
    else
    {
        int mij = (st + dr) / 2;

        if(c <= mij)
        {
            update(nod * 2, st, mij);
        }
        else
        {
            update(nod * 2 + 1, mij + 1, dr);
        }

        arb[nod] = arb[nod * 2] + arb[nod * 2 + 1];
    }
}

int query(int nod, int st, int dr)
{
    if(st == dr)
    {
        return st;
    }

    int mij = (st + dr) / 2;

    if(v[i] > (mij - st + 1) - arb[nod * 2])
    {
        v[i] -= ((mij - st + 1) - arb[nod * 2]);

        return query(nod * 2 + 1, mij + 1, dr);
    }

    return query(nod * 2, st, mij);
}

int main()
{
    std :: iostream :: sync_with_stdio(false);

    in.tie(NULL);

    out.tie(NULL);

    in >> n;

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

    std :: reverse(v + 1, v + n + 1);

    for(i = 1; i <= n; i ++)
    {
        c = query(1, 1, n);

        update(1, 1, n);

        ans.push_back(std :: make_pair(c, n - i + 1));
    }

    std :: sort(ans.begin(), ans.end());

    for(auto i : ans)
    {
        out << i.second << '\n';
    }

    return 0;
}