Cod sursa(job #2099178)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 4 ianuarie 2018 02:44:54
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include<iostream>
#include<fstream>
using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");

const int N = 30001;
int v[N], sol[N], aib[N];
int n;

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

void update(int index, int value){
    if(index < N){
        aib[index] += value;
        update(index + lsd(index), value);
    }
}

void print_aib(){
    for(int i=1; i<=n; ++i)
        cout<<aib[i]<<" "; cout<<"\n";
}

int query(int dr){ /// [1, dr]
    int index = dr;
    int sum = 0;

    while(index > 0){
        sum += aib[index];
        index -= lsd(index);
    }

    return sum;
}

int query_interval(int st, int dr){ /// [st, dr]
    return query(dr) - query(st-1);
}

int firstIndexOf(int x){
    int st = 1;
    int dr = n;

    while(st < dr){
        int mij = (st+dr) / 2;
        int value = query(mij);

        if(x <= value) /// Keep looking (left)
            dr = mij;
        else if(x > value) /// Keep looking (right)
            st = mij+1;
    }

    if(query(st) != x)
        return -1;
    else{ /// FIXME: Binary search this value!
        while(query(st-1) == x)
            --st;
        return st;
    }
}

int main()
{
    /*n = 8;

    update(1, 1);
    update(4, 1);
    for(int i=1; i<=n; ++i)
        cout<<"[1, "<<i<<"] = "<<query(i)<<"\n";

    for(int i=1; i<=query(n); ++i)
        cout<<i<<" --> "<<firstIndexOf(i)<<"\n";

    return 0;*/

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

    for(int i=1; i<=n; ++i)
        update(i, 1);

    for(int i=n; i>=1; --i)
    {
        //if(i%100 == 0) cout<<i<<"\n";
        int index = firstIndexOf(v[i]);
        //cout<<i<<" --> "<<index<<"\n";
        sol[index] = i;
        update(index, -1);
    }

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

    /*update(1, 1);
    update(2, 1);
    update(5, 1);
    update(7, 1);


    for(int i=1; i<=n; ++i)
        cout<<"[1, "<<i<<"] = "<<query(i)<<"\n";

    for(int i=1; i<=query(n); ++i)
        cout<<i<<" --> "<<firstIndexOf(i)<<"\n";*/

    return 0;
}