Cod sursa(job #991130)

Utilizator harababurelPuscas Sergiu harababurel Data 29 august 2013 20:12:50
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 30005
using namespace std;

int n, presumedPos, actualPos, l, s;
int H[3*nmax], v[nmax], sol[nmax];


void update(int node, int lo, int hi, int pos) {
    if(lo == hi) {
        H[node]++;
        return;
    }

    int mid = (lo + hi) >> 1;

    if(pos <= mid) update(2*node, lo, mid, pos);
    else update(2*node+1, mid+1, hi, pos);

    H[node] = H[2*node] + H[2*node+1];
}

int sum(int node, int lo, int hi, int a, int b) {
    if(a <= lo && hi <= b) return H[node];

    int mid = (lo + hi) >> 1, ret = 0;
    if(a <= mid) ret += sum(2*node, lo, mid, a, b);
    if(b > mid)  ret += sum(2*node+1, mid+1, hi, a, b);

    return ret;
}

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--) {
        presumedPos = v[i];
        actualPos = presumedPos;
        l = 0;
        s = 1;

        while(s) {
            s = sum(1, 0, n, l, presumedPos);
            actualPos += s;
            l = presumedPos+1;
            presumedPos = actualPos;
        }

        //cout<<i<<": in="<<v[i]<<"; actualPos="<<actualPos<<"; sum = "<<actualPos-presumedPos<<"\n";

        sol[actualPos] = i;
        update(1, 0, n, actualPos);
    }

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



    return 0;
}