Cod sursa(job #996799)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 12 septembrie 2013 17:41:06
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
using namespace std;

const int MAX_N = 30002;

int N;
int A[MAX_N], sol[MAX_N], v[MAX_N];


inline void Update(int pos, int val) {
    while(pos <= N) {
        A[pos] += val;
        pos += pos&(pos^(pos-1));
    }
}

inline int Query(int pos) {
    int Sum = 0;
    while(pos > 0)
        Sum += A[pos], pos -= pos&(pos^(pos-1));

    return Sum;
}

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

    f >> N;
    for(int i = 1; i <= N; ++i)
        f >> v[i];

    for(int i = N; i >= 1; --i) {
        int t = v[i], l = 0;
        while(Query(l) != Query(t)) {
            int temp = t;
            t += Query(t) - Query(l);
            l = temp;
        }
        sol[t] = i;
        Update(t, 1);
    }

    for(int i = 1; i <= N; ++i)
        g << sol[i] << "\n";

    f.close();
    g.close();

    return 0;
}