Cod sursa(job #826829)

Utilizator cdascaluDascalu Cristian cdascalu Data 1 decembrie 2012 12:05:11
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#define Nmax 30001
using namespace std;

short int N,v[Nmax],q,sol[Nmax],AIB[Nmax];
void read_data()
{
    ifstream f("schi.in");
    f>>N;
    int i;
    for(i=1;i<=N;++i)
        f>>v[i];
    f.close();
}
void write_data()
{
    ofstream g("schi.out");
    for(int i=1;i<=N;++i)
        g<<sol[i]<<"\n";
    g.close();
}
int bit(int x)
{
    return (x&(x-1))^x;
}
short int query(int x)//pe intervalul 1 i tin nr de pozitii sterse
{
    int i;
    short int s;
    for(i=x,s=0;i>=1;i-=bit(i))
        s+=AIB[i];
    return s;
}
void update(int x)
{
    int i;
    for(i=x;i<=N;i+=bit(i))
        ++AIB[i];
}
short int check(int val)
{
    int step,i;
    for(step=1;step<N;step <<=1 );
    for(i = N;step;step >>= 1)
        if(i-step >= 1 && (i - step) - query(i-step) >= val)
            i-=step;

    return i;
}
int main()
{
    read_data();
    int i;
    for(i=N;i>=1;--i)
    {
        q           = check(v[i]);//a v[i]-a pozitie libera
        sol[q]      = i;//este ocupata de concurentul i
        update(q);
    }
    write_data();
    return 0;
}