Cod sursa(job #1763760)

Utilizator preda.andreiPreda Andrei preda.andrei Data 24 septembrie 2016 16:22:43
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

inline int PutereZerouri(int x)
{
    return (x ^ (x - 1)) & x;
}

bool Compara(const pair<int, int> &p1, const pair<int, int> &p2)
{
    return p1.first < p2.first;
}

void Adauga(vector<int> &aib, int poz, int val)
{
    while (poz < aib.size()) {
        aib[poz] += val;
        poz += PutereZerouri(poz);
    }
}

int AflaSuma(const vector<int> &aib, int poz)
{
    int suma = 0;
    while (poz > 0) {
        suma += aib[poz];
        poz -= PutereZerouri(poz);
    }
    return suma;
}

int GasesteLoc(vector<int> &aib, int k)
{
    int loc = 0;
    int putere = (1 << 18);

    while (putere > 0) {
        if (loc + putere < aib.size() && AflaSuma(aib, loc + putere) < k)
            loc += putere;
        putere >>= 1;
    }
    ++loc;

    Adauga(aib, loc, -1);
    return loc;
}

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

    int n;
    fin >> n;

    vector<int> aib(n + 1);
    for (int i = 1; i <= n; ++i)
        Adauga(aib, i, 1);

    vector<int> locuri(n + 1);
    vector<pair<int, int>> rezultate;

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

    for (int i = n; i >= 1; --i) {
        int loc_final = GasesteLoc(aib, locuri[i]);
        rezultate.push_back({loc_final, i});
//        cout << i << " e pe locul " << loc_final << "\n";
//        for (int j = 1; j <= n; ++j)
//            cout << j << "(" << AflaSuma(aib, j) << ")  ";
//        cout << "\n";
    }

    sort(rezultate.begin(), rezultate.end(), Compara);
    for (auto r : rezultate)
        fout << r.second << "\n";

    return 0;
}