Cod sursa(job #826840)

Utilizator cdascaluDascalu Cristian cdascalu Data 1 decembrie 2012 12:10:15
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#define Nmax 30001
using namespace std;

int N,v[Nmax],q,sol[Nmax],AIB[Nmax];
void read_data()
{
    FILE*f = fopen("schi.in","r");
    fscanf(f,"%d",&N);
    int i;
    for(i=1;i<=N;++i)
        fscanf(f,"%d",&v[i]);
    fclose(f);
}
void write_data()
{
    FILE*g = fopen("schi.out","w");
    for(int i=1;i<=N;++i)
        fprintf(g,"%d\n",sol[i]);
    fclose(g);
}
inline int bit(int x)
{
    return (x&(-x));
}
int query(int x)//pe intervalul 1 i tin nr de pozitii sterse
{
    int i;
    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];
}
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;
}