Cod sursa(job #826801)

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

short 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);
}
short int bit(short int x)
{
    return (x&(x-1))^x;
}
short int query(int x)//pe intervalul 1 i tin nr de pozitii sterse
{
    short 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(short int val)
{
    short int left,right,mid,res,sol;
    left = 1;
    right = N;
    while(left<=right)
    {
        mid = (left+right)/2;
        res = mid - query(mid);//nr de 1 din (1,mid)
        if(res == val)
            sol = mid;

        if(res>=val)
            right = mid-1;
        else
            left = mid+1;
    }
    return sol;
}
int main()
{
    read_data();
    short 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;
}